中缀表达式求值
一不小心断更这么久了，不要说我懒，看这篇文章的肯定有比我更懒的hhhhh。趁着偶然的机会，恰巧赶上考研复习到栈，搞一搞数据结构吧(Φ皿Φ)
关于这次的题目
实际的问题是“表达式求值”这五个字，我就把它简单化理解了。实现十进制数中缀表达式（普通的表达式）的四则运算。这样也很好地应用了栈的功能，当个练习了。
对中缀表达式直接求值比较复杂也少见，所以把这个问题分为两步：将中缀表达式转化为后缀表达式和对后缀表达式求值。两个过程都需要用到栈。
中缀表达式转化为后缀表达式
相关代码如下
bool compare(char a,char b)//比较操作符a和b的优先级
{
if(a=='*'||a=='/'){
if(b=='*'||b=='/') return false;
else
return true;
}
else
return false;
}
void get_sexp(string s)
{
cout<<"Suffix Expression: ";
stack<char> ope_stack;//操作符栈
int len=s.length();
for(int i=0;i<len;i++){//顺序取出中缀表达式字符
char t=s[i];
if(t=='(') ope_stack.push(s[i]);
else if(t==')'){
char ope=ope_stack.top();
while(ope!='('){
sexp[z++]=ope;
cout<<ope<<" ";
ope_stack.pop();
ope=ope_stack.top();
}
ope_stack.pop();//'('出栈
}
else if(t>='0'&&t<='9'){
sexp[z++]=t;
cout<<t<<" ";
}
else{
if(ope_stack.empty()) ope_stack.push(t);
else{
char stp=ope_stack.top();
if(stp=='('||compare(t,stp)) ope_stack.push(t);
else{
while(!compare(t,stp)&&!ope_stack.empty()&&stp!='('){
ope_stack.pop();
cout<<stp<<" ";
sexp[z++]=stp;
if(!ope_stack.empty())
stp=ope_stack.top();
}
ope_stack.push(t);
}
}
}
}
while(!ope_stack.empty()){
char t=ope_stack.top();
cout<<t<<" ";
sexp[z++]=t;
ope_stack.pop();
}
}
转化方法：利用一个辅助栈，将操作符（“+”、“-”、“*”、“/”、“(”、“)”）进行栈操作
第一步，顺序取出中缀表达式的字符：
-
若是数字，直接输出；
-
若是“(”，将其压栈；
-
若是“)”， 将栈中的四则运算符出栈并输出，直到遇到“(”，将“(”出栈但不输出；
-
若是四则运算符，将其与栈顶运算符进行比较：有以下三种情况
① 如果它比栈顶的操作符优先级高，或者它是左括号后的第一个操作符，则将其压栈；
② 如果它比栈顶的操作符优先级低或相等， 将栈顶操作符弹出并输出；
③ 继续比较，如果它比新的栈顶操作符的优先级高，继续下一步骤，否则，重复上一步。
第二步，判断是否取到了中缀表达式的末尾，若是，将栈中的剩余的运算符全部出栈并输出，若不是则重复第一步。
为转化后的后缀表达式求值
相关代码如下
void calculate(string s){
stack<float> val_stack;
val_stack.push(1.0*(sexp[0]-'0'));//将字符转化为浮点型数
for(int i=1;i<z;i++){
char t=sexp[i];
if(t>='0'&&t<='9') val_stack.push((t-'0')*1.0);
else{
float x=val_stack.top(); val_stack.pop();
float y=val_stack.top(); val_stack.pop();
float tmp;
if(t=='+') tmp=x+y;
else if(t=='-') tmp=y-x;
else if(t=='*') tmp=x*y;
else tmp=y/x;
val_stack.push(tmp);
}
}
cout<<endl<<s<<" = "<<val_stack.top()<<endl;
}
int main(){
string in_exp;
cout<<"Please enter an expression:";
cin>>in_exp;//输入(中缀)表达式
get_sexp(in_exp);//得到后缀表达式
calculate(in_exp);//计算返回结果
return 0;
}
第一步，顺序取出后缀表达式
1. 当取到数字时，将其压入栈；
2. 当取到运算符时，将两个数字出栈并进行计算，将运算结果压栈。
当取到后缀表达式结尾计算结果时，栈顶元素就是表达式的值。
这里标注一下，将字符转化为浮点数的代码。是先将字符型转化为整型，再由整型转化为浮点型。关于字符型转为整型的原理和ASCII码有关，可自行Google
测试
可了
后记
做个练习确实对原理的理解很有帮助，可能之后会时不时搞一搞。
