实现中缀表达式转换为后缀表达式，再求值
[ 本帖最后由 Mr.K 于 2014-11-9 00:04 编辑 ]\n\n#include <stdio.h>#include <malloc.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
typedef char DataType;
//定义结构体
typedef struct snode
{
DataType data;
struct snode *next;
}LSNode;
//初始化
void StackInitiate(LSNode **head)
{
*head = (LSNode *)malloc(sizeof(LSNode));
(*head)->next = NULL;
}
//非空否
int StackNotEmpty(LSNode *head)
{
if(head->next == NULL) return 0;
else return 1;
}
//入栈
void StackPush(LSNode *head,DataType x)
{
LSNode *p;
p = (LSNode *)malloc(sizeof(LSNode));
p->data = x;
p->next = head->next;
head->next = p;
}
//出栈
int StackPop(LSNode *head,DataType *d)
{
LSNode *p = head->next;
if(p == NULL)
{
// printf("堆栈已空出错！");
return 0;
}
head->next = p->next;
*d = p->data;
free(p);
return 1;
}
//取栈顶数据元素+修改返回栈顶元素
char StackTop(LSNode *head,DataType *d)
{
LSNode *p = head->next;
if(p == NULL)
{
// printf("堆栈已空出错！");
return 0;
}
*d = p->data;
// return 1;
return *d;
}
//撤销动态申请空间
void Destroy(LSNode *head)
{
LSNode *p,*p1;
p = head;
while(p != NULL)
{
p1 = p;
p = p->next;
free(p1);
}
}
//后缀算术表达式的求值函数
int PostExp(char str[])
{
DataType x,x1,x2;
int i;
LSNode *head;
StackInitiate(&head);
for(i = 0; str != '#'; i++)
{
if(isdigit(str))//???
{
x = (int)(str-48);//???
StackPush(head,x);
}
else
{
StackPop(head,&x2);
StackPop(head,&x1);
switch(str)
{
case'+':{ x1 += x2; break; }
case'-':{ x1 -= x2; break; }
case'*':{ x1 *= x2; break; }
case'/':
if(x2 == 0.0)
{
printf("除数为0错！\n");
exit(0);
}
else
{
x1 /= x2;
break;
}
}
StackPush(head,x1);
}
}
StackPop(head,&x);
return x;
}
//////////////////////////////////////////////////////////////////////////
//验证是否为操作符
bool IsOperator(char ch)
{
char ops[] = "+-*/";
for(int i = 0; i < sizeof(ops); i++)
{
if(ch == ops) return true;
}
return false;
}
// 比较两个操作符的优先级
int Precedence(char op1,char op2) //op1代表栈顶运算符，op2代表当前扫描读到的运算符
{
if(op1 == '#') return -1;
if(op1 == '(') return -1;
if(op1 == '+' || op1 == '-')
{
if(op2 == '*' || op2 == '/') return -1;
else return 0;
}
if(op1 == '*' || op1 == '/')
{
if(op2 == '+' || op2 == '-') return 1;
else return 0;
}
if(op1 == '+' || op1 == '-')
{
if(op2 == '+' || op2 == '-') return 0;
else return -1;
}
}
//中缀表达式转换成后缀表达式
void inFix2postFix(char *inFix,char *postFix)
{
int len,i,j = 0;
char c,c1;
LSNode *head; //定义头指针变量head
StackInitiate(&head); //初始化链式堆栈head
len = strlen(inFix);
StackPush(head,'#'); //将“#”压入栈顶,防止堆栈已空，报错
for(i = 0;i < len; i++)
{
c = inFix;
if(c == '(') StackPush(head,c); //c入栈
else if(c == ')') //“）”任一个操作符都低级
{
while(StackTop(head,&c1) != '(') //取栈顶元素
{
postFix = StackTop(head,&c1);//将在“（”之后的操作符放到后缀表达式
StackPop(head,&c1); //并把它出栈
}
StackPop(head,&c1); //把“（”出栈
}
else
{
if(!IsOperator(c))postFix = c; //条件：不是操作符（即操作数），执行第一条语句
else
{
if(StackTop(head,&c1) == '#')
{
StackPush(head,c); //将操作符压入栈顶
}
else
{
while(StackNotEmpty(head) == 1
&& Precedence(StackTop(head,&c1),c) >= 0)
{
postFix = StackTop(head,&c1);
StackPop(head,&c1);
}
StackPush(head,c); //将操作符压入栈顶
}
}
}
}
while(StackNotEmpty(head) == 1) //弹出所有操作符
{
postFix = StackTop(head,&c);
StackPop(head,&c1);
}
postFix = '\0'; //字符数组添加结束符
}
//////////////////////////////////////////////////////////////////////////
void main(void)
{
char str[] = "3642/-5*+#",str1[] = "3+(6-4/2)*5",str2;
inFix2postFix(str1,str2); //对中缀表达式进行转换，再计算
int result,result2;
printf("%s\n",str2);
result = PostExp(str);
result2 = PostExp(str2);
printf("\n\n\n\n（直接对后缀表达式的运算）后缀算术表达式计算结果：%d\n",result);
printf("\n\n\n\n（间接对中缀表达式的运算）后缀算术表达式计算结果：%d\n",result2);
}
页:
[1]