算术中缀表达式求值（栈实现）

曾经终败给现在 2022-06-06 03:40 243阅读 0赞

**问题描述：**

输入由整型分量和操作符组成的中缀表达式，输出其后缀表达式和运算的结果。整型分量：十进制数。操作符：( , ) , + , - , \* , / 。

如输入3\*(5-8/2)+7，输出 3 5 8 2 / - \* 7 +，结果是10;  
输入3-(1/4+7)\*3 ,输出 3 1 4 / 7 + 3 \* -，结果是 -18.75；  
输入3\*4/5\*(5-7)+4，输出 3 4 \* 5 / 5 7 - \* 4 +，结果是-0.8。

注意：输入的运算分量为十进制数，输出可能是小数。

**问题分析：**

中缀表达式难以直接求值，要通过转化为其后缀表达式计算。转化和求值过程都需要借助STL的STACK来实现。

**转化：**

1）顺序扫描中缀表达式，

*  当遇到一个左括号时立即将其压栈；
 *  当遇到对应的右括号时，将栈中的操作符弹出并输出，直到遇到左括号。最后再弹出左括号（但不输出）；
 *  当遇到一个分量时，立即输出；
 *  当遇到一个操作符时，将它与栈顶操作符比较：

<1>如果它比栈顶的操作符优先级高，或者它是左括号后的第一个操作符，则将其压入栈；

<2>否则（低或相等），将栈顶操作符弹出并输出；

<3>继续比较，如果它比新的栈顶操作符的优先级高，跳到 2），否则，重复<2> <3>。

2）如果扫描到了中缀表达式的末尾，将栈中的剩余的操作符全部弹出并输出，否则重复 1）。

**求值：**

中缀表达式的求值需要其后缀表达式（可用char 型的数组保存）和一个运算分量栈，借用后缀表达式求值也体现了其价值。

1）顺序扫描后缀表达式，

当遇到运算分量时将其压入运算分量栈；

当遇到运算符时，弹出两个运算分量进行计算，并将结果压栈。

2）当扫描到后缀表达式末尾再次计算结果时，栈顶元素就是所求表达式的值，否则，重复 1）。

**C++ code：**

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    char suf_exp[100];//储存后缀表达式
    int z=0;//suf_exp的下标变量
    
    bool cmp(char a,char b){//若操作符a和b的优先级
        if(a=='*'||a=='/'){//a的高
            if(b=='*'||b=='/')  return false;
            else
                return true;
        }
        else//b的高
            return false;
    }
    void get_suf_exp(string s){
        cout<<"It's suffix expression: ";
        stack<char> ope_stack;//操作符栈
        int len=s.length();
        for(int i=0;i<len;i++){//1)
            char t=s[i];
            if(t=='(')   ope_stack.push(s[i]);
            else if(t==')'){
                char ope=ope_stack.top();
                while(ope!='('){
                    suf_exp[z++]=ope;
                    cout<<ope<<" ";
                    ope_stack.pop();
                    ope=ope_stack.top();
                }
                ope_stack.pop();//pop '('
            }
            else if(t>='0'&&t<='9'){
                suf_exp[z++]=t;
                cout<<t<<" ";
            }
            else{
                if(ope_stack.empty())    ope_stack.push(t);
                else{
                    char stp=ope_stack.top();
                    if(stp=='('||cmp(t,stp))  ope_stack.push(t);// 1)<1>
                    else{                                       // 1)<2> <3>
                        while(!cmp(t,stp)&&!ope_stack.empty()&&stp!='('){
                            ope_stack.pop();
                            cout<<stp<<" ";
                            suf_exp[z++]=stp;
                            if(!ope_stack.empty())
                                stp=ope_stack.top();
                        }
                        ope_stack.push(t);
                    }
                }
            }
        }
        while(!ope_stack.empty()){//2)
            char t=ope_stack.top();
            cout<<t<<" ";
            suf_exp[z++]=t;
            ope_stack.pop();
        }
    }
    
    void calculate(string s){
        stack<float> val_stack;
        val_stack.push(1.0*(suf_exp[0]-'0'));//将字符转化为浮点型数
        for(int i=1;i<z;i++){
            char t=suf_exp[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<<tmp;
            }
        }
        cout<<endl<<s<<" = "<<val_stack.top()<<endl;
    }
    int main(){
        string in_exp;//输入中缀表达式
        cin>>in_exp;
        get_suf_exp(in_exp);
        calculate(in_exp);
        return 0;
    }