表达式求值

一.关于三种表达式的分类

• 中缀表达式：即我们最为常见的表达式，运算符号位于参与运算的连个操作数中间的表达式称作中缀表达式
• 前缀表达式：前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。
• 后缀表达式：指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则），后缀表达式也称为逆波兰表达式。

二.表达式的求值算法

1.中缀表达式的求值算法：

假设参与运算的表达式是由+ - * \ ( )这6种符号构成的

规定运算符的优先级：

• 运算符）的优先级最低，
• 运算符*，\的优先级相同，运算符+，-的优先级相同，且*，\的优先级大于+，-
• 运算符(的优先级比较特殊，当（作为入栈元素时，它的优先级最大，即无条件入栈；而当（作为栈顶元素时，它的优先级最小，即除运算符）以外的所有运算符无条件入栈
• 当栈顶元素为（，入栈元素为）时，两运算符在符号栈中相抵消。

假设θ1是栈顶元素，θ2是入栈元素，那么具体的运算符优先级关系比较可由下表体现：

在求值算法中，我们需要用到两个栈来帮助计算：
其中一个称为运算数栈，用来存放参与运算的数，简称OPND(operand)
另一个称为运算符栈，用来存放参与运算的运算符，简称OPTR(operator）

正式算法描述如下：

首先初始化两个栈，然后从中缀表达式按照从左往右的顺序去取符号c，

如果取到的是运算数，则将c放入OPND中入栈；
如果取到的是运算符，则加以判断：

• 如果OPTR栈空，则将c入栈OPTR
• 如果c的优先级大于OPTR的栈顶元素，则将c入栈OPTR
• 如果c的优先级小于OPTR的栈顶元素，则从栈OPTR中以此出栈两个运算数n1，n2，做n2 c n1的运算后将得到的结果n入栈OPND
• ‘（’和’）‘的情况可特殊处理，如果栈顶元素和入栈元素分别为’（‘和’）‘时，相消即可

当操作数栈空并且表达式被全部读取完毕时，计算结束，可以获得最终求值结果

下面列出算法代码：

关于栈的定义和基本操作：

//栈的定义 
typedef struct stack
{char elements[100];int top;int size;
}stack;//栈的基本操作 
void InitStack(stack *s)
{s->top=0;s->size=0;
}void Push(stack *s,char c)
{s->elements[s->top++]=c;s->size++;
}void Pop(stack *s,char *c)
{*c=s->elements[--s->top];s->size--;
}void Top(stack *s,char *c)
{*c=s->elements[s->top-1];
}int isEmpty(stack *s)
{if(s->top==0)return 1;else return 0;
}

求值算法：

//中缀表达式求值算法 
int Calculate_InfixExpression(char *s,int length)
{stack OPND,OPTR;InitStack(&OPND);InitStack(&OPTR);int i=0;char a,b,c,t,result;while(s[i]!=0||!isEmpty(&OPTR)){c=s[i++];if(c>='0'&&c<='9'){Push(&OPND,c);}else{Top(&OPTR,&t);if(isEmpty(&OPTR)) 	Push(&OPTR,c);else{switch(compare(t,c)){case -1: {Push(&OPTR,c);break;}case 1:{Pop(&OPTR,&t);Pop(&OPND,&a);Pop(&OPND,&b);Push(&OPND,opreate(a,b,t));i--;break;}case 0:{Pop(&OPTR,&t);break;}		}}}}	Top(&OPND,&result);return result-'0';
}

补充算法中的两个函数，运算符优先级的比较函数和操作数的计算函数：

//运算符比较函数 
int compare(char c1, char c2)
{if(c1=='('&&c2==')') return 0;else if(c1=='('||c2=='(') return -1;else if(c1=='*'||c1=='/') return 1;else if(c1=='+'||c1=='-'){if(c2=='*'||c2=='/') return -1;else return 1;}
}//运算操作函数
char opreate(char n,char m,char c) 
{int a=n-'0';int b=m-'0';switch(c){case '+':return b+a+'0';case '-':return b-a+'0';case '*':return b*a+'0';case '/':return b/a+'0';}
}

主函数调用及运算效果：

main()
{char s[]="3+2*(7-2)+(2+1)*3";int result = Calculate_InfixExpression(s,strlen(s));printf("%s = %d",s,result);
}

2.后缀表达式的求值算法

后缀表达式的求值算法比较简单，利用单独的栈即可完成计算：
从左向右扫描后缀表达式：

• 如果遇到的是运算数，则入栈
• 如果遇到的是运算符o，则从栈中依次出栈两个元素：a，b；将b o a 的结果入栈
• 最终当栈中只剩一个元素时，即为最后所求结果

c语言的算法实现，目的是表达算法逻辑，所以为了简单，只支持单步操作结果在255以内的计算，原因是栈的元素类型是char

int calculate(char *src) 
{stack s;InitStack(&s);int length=strlen(src),i=0;char c,a,b,result;for(i=0;i<length;i++){c=src[i];if(c>='0'&&c<='9'){Push(&s,c);}else{Pop(&s,&a);Pop(&s,&b);Push(&s,opreate(a,b,c));}}if(!isEmpty(&s)) Pop(&s,&result);return result-'0';}

三.中缀表达式到后缀表达式的转换

1.利用栈进行转换的算法

算法描述如下：
我们借助一个操作符栈来进行转换运算，并将转换结果存入一个结果队列当中
从左到右按顺序扫描中缀表达式：

• 如果扫描到的是运算数，则将运算数直接存入结果队列
• 如果扫描到的是’('，则直接将其入栈，入栈后其拥有最低的优先级
• 如果扫描到的是’)‘，则将栈中存在于’('之前的所有运算符依次出栈并入队，‘('也出栈但不入队
• 如果遇到的是一般运算符，则将其与栈顶运算符比较：如果其优先级高于栈顶运算符的优先级，则将其入栈；否则将栈顶运算符出栈并入队，直到栈顶运算符优先级小于该运算符为止
• 当扫描结束时，如果运算符栈不为空，则将其中元素全部出栈并入队

最终结果队列中存放的就是转换后的后缀表达式

给出后缀表达式算法的c语言实现：

char *conversion(char * src)
{stack s;InitStack(&s);int length=strlen(src),i=0,j=0,k;char c,t,*dst=(char *)malloc(sizeof(char)*length);for(i=0;i<length;i++){c=src[i];if(c>='0'&&c<='9'){dst[j++]=c;}else if(c=='('){Push(&s,c);}else if(c==')'){Top(&s,&t);while(t!='('){Pop(&s,&t);if(t!='(')  dst[j++]=t;else break;	}}else{if(isEmpty(&s)){Push(&s,c);}else{Top(&s,&t);switch(compare(t,c)){case -1: Push(&s,c);break;case 1: {while(compare(t,c)==1){Pop(&s,&t);dst[j++]=t;if(isEmpty(&s)) break;Top(&s,&t);}Push(&s,c);	}break;}}}}while(!isEmpty(&s)){Pop(&s,&t);dst[j++]=t;}return dst;
}main()
{char * src="2+3*4+(6*8+7)*5";char *dst=conversion(src);printf("后缀表达式为：%s ",dst);} 

运行结果如下：