表达式求值
表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子。这里介绍 “算符优先法” 进行求解。
对算术表达式求值，首先要了解四则运算规律
（1）先乘除，后加减
（2）从左到右
（3）先括号内，后括号外
~~算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行
这里讨论只含加减乘除4种运算，基于整数范围且语法正确的表达式
求解分两步
一：构造算符间优先关系表格
（1 ) 开二维数组存上图关系表格
// 开二维数组存表
char priority[7][7]={
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','0'}, // 此行"(" = ")"表示左右括号相遇，括号内运算已完成
{'>','>','>','>','0','>','>'},
{'<','<','<','<','<','0','='} // “#" = "#” 表示整个表达式求值完毕
}; // "0"表示不可能出现这种情况 ( 语法错误 )
(2) // 建立 priority [ ] [ ] 和 +、 -、 *、 / 运算符间的映射关系
char Procede(char a,char b){
int i,j;
switch(a){
case'+':i=0;break;
case'-':i=1;break;
case'*':i=2;break;
case'/':i=3;break;
case'(':i=4;break;
case')':i=5;break;
case'#':i=6;break; // # 是表达式的结束符
}
switch(b){
case'+':j=0;break;
case'-':j=1;break;
case'*':j=2;break;
case'/':j=3;break;
case'(':j=4;break;
case')':j=5;break;
case'#':j=6;break;
}
return priority[i][j];
}
“#“是表达式的结束符，为了算法简洁，在表达式最左边也虚设一个“#”构成表达式的一对括号。表中”(”=”)"表示左右括号相遇时，括号内的运算已经完成。同理，“#”=“#”表示整个表达式求值完毕，表中的0表示语法错误，在此不讨论。
二：算符优先算法的实现
- 为实现算符优先算法，使用两个栈。一个OPTR栈（Operator stack），用于寄存运算符；一个OPND栈（Operand stack），用于寄存操作数或运算结果。
---------------------------------- 算法基本思想------------------------------------- - （1）首先置操作数栈为空栈，表达式起始符 “#” 为运算符的栈底元素
- （2）依此读入表达式中的每个字符，若是操作数则入OPND栈，若是运算符则和OPTR栈的栈顶运算符进行比较优先权后进行相应操作，直至整个表达式求值完毕（即OPTR的栈顶元素和当前读入的字符均为 “#”）。
- 伪代码
while(c!='#'||OPTR.top()!='#'){ //只要表达式未读完或者运算符栈未运算完
int y=0;
if(c>='0'&&c<='9'){
while(c>='0'&&c<='9'){ // 用while可读取超过一位数字
y=y*10+(c-'0');
c=s[k++];
}
OPND.push(y); // 把读进的数字入数字栈
}
else{
switch(Procede(OPTR.top(),c))
{
case'<': // 栈顶元素优先权低
OPTR.push(c);
c=s[k++];
break;
case'=':
OPTR.pop(); // 脱括号
c=s[k++]; // 读下一个字符
break;
case'>': //退栈并将运算结果入栈
char x=OPTR.top();OPTR.pop();
int m=OPND.top();OPND.pop();
int n=OPND.top();OPND.pop();
OPND.push(Operate(m,n,x));
break;
} //switch
}//else
}//while
cout<<OPND.top();
完整代码如下：
//算符优先法
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=110;
char priority[7][7]={
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','0'}, // 此行"("=")"表示左右括号相遇，括号内运算已完成
{'>','>','>','>','0','>','>'},
{'<','<','<','<','<','0','='} // "=" 表示整个表达式求值完毕
}; // "0"表示不可能出现这种情况 ( 语法错误 )
//Precede 用于判断运算符栈栈顶运算符 a1 与读入运算符 a2 之间的优先关系函数
char Procede(char a,char b){ // 建立 pre[][] 到 运算符间的映射关系
int i,j;
switch(a){
case'+':i=0;break;
case'-':i=1;break;
case'*':i=2;break;
case'/':i=3;break;
case'(':i=4;break;
case')':i=5;break;
case'#':i=6;break; // # 是表达式的结束符
}
switch(b){
case'+':j=0;break;
case'-':j=1;break;
case'*':j=2;break;
case'/':j=3;break;
case'(':j=4;break;
case')':j=5;break;
case'#':j=6;break;
}
return priority[i][j];
}
int Operate(int m,int n,char x){
if(x=='+')
return m+n;
if(x=='-')
return n-m;
if(x=='*')
return m*n;
if(x=='/')
return n/m;
}
// EvaluuateExpression-reduced
int main(){
stack <int> OPND; // Operand stack
stack <char> OPTR; // Operator stack
OPTR.push('#');//
char ss[2]="#";//尾部有\0
char s[maxn];
cin>>s;
strcat(s,ss);// 运算式尾部加 "#"--结束运算符
char c=s[0];
int k=1;
while(c!='#'||OPTR.top()!='#'){ //表达式未读完或者运算未完
int y=0;
if(c>='0'&&c<='9'){
while(c>='0'&&c<='9'){ // 读入连续的数字
y=y*10+(c-'0');
c=s[k++];
}
OPND.push(y); // 把读进的数字入数字栈
}
else{
switch(Procede(OPTR.top(),c))
{
case'<': //栈顶元素优先权低
OPTR.push(c);
c=s[k++];
break;
case'=':
OPTR.pop(); // 脱括号
c=s[k++]; // 读入下一个字符
break;
case'>': //退栈并将运算结果入栈
char x=OPTR.top();OPTR.pop();
int m=OPND.top();OPND.pop();
int n=OPND.top();OPND.pop();
OPND.push(Operate(m,n,x));
break;
}
}
}
cout<<OPND.top();
return 0;
}
测试结果：
参考资料：数据结构（C语言版） 严蔚敏 等