数据结构-表达式求值 （C++代码）

解题思路:

问题描述：

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

如输入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++STL；

参考代码:

#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;

}