题解 | #表达式求值#

一.题意整理

给出一个含有加减乘除和括号的表达式的字符串，求出该字符串的值。(运算符合运算法则，先乘除后加减)

二.思路整理

利用栈来求表达式是栈的一种基本运用，下面我们将会介绍如何利用栈来解决表达式求值的问题：

对于算术表达式一般分成三种有：前缀、后缀和中缀
中缀表达式：救是我们常见的算术表达式，就是一眼看上去就能理解的表达式，例如：2*(5+8)
前缀表达式：形如"op A B"即操作数在两个运算数的前面
后缀表达式：形如"A B op"即操作数在两个运算数的后面

下面给出计算表达式的核心思路：对于一个表达式，也就是对于一个中缀表达式我们可以先将表达式转换成后缀表达式，然后对这个后缀表达式求值。

中缀表达数转后缀表达式：
1.建立一个存储运算符的栈，对中缀表达式进行扫描。
(1)如果遇到一个数就直接存进后缀表达式中。
(2)如果遇到了一个左括号，就把左括号直接入栈。
(3)如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后左括号出栈。
(4)如果遇到运算符，只需要栈顶符号的优先级补丁与新符号，就不断出栈并输出，然后将新符号入栈。
2.依次取出并存储栈中所有剩余的符号。

后缀表达式求值：
1.建立一个用于存储的数的栈，对后缀表达式进行依次扫描
(1)如果遇见一个数，那么就把这个数直接入栈
(2)如果遇到运算符，就取出栈顶的两个数进行计算，然后把结果入栈。
2.最后的栈顶元素就是表达式的值

三.代码实现

class Solution {
public:
   int solve(string s) {
       /*
       为什么这块要用string 而不是char?
       只用利用结点为string的vecter可以方便的表示字符和数字
       对于式数字的string可以利用stoi函数来进行转换
       */
       unordered_map<string,int>mp;//用来记录优先级
       mp["*"]=1;
       mp["+"]=0;
       mp["+"]=0;
       stack<string>op;//中缀表达式转化为后缀表达式中符号栈
       stack<int>num;//后缀表达式求值中需要的数字栈
       string str="";
       vector<string>ss;//后缀表达式
       //中缀表达式转换为后缀表达式
       for(int i=0;i<s.size();i++){
           if(!isdigit(s[i])){
               if(str!=""){
                   ss.push_back(str);
                   str="";
               }
           }
           if(isdigit(s[i])){
              str+=s[i];
           } else {
               if(s[i]=='('){
                   string now="";
                   now+=s[i];
                   op.push(now);
               } else if(s[i]==')'){
                   while(op.size()&&op.top()!="("){
                       ss.push_back(op.top());
                       op.pop();
                   }
                   op.pop();
               } else {
                   string now="";
                   now+=s[i];
                   while(op.size()&&op.top()!="("&&mp[now]<=mp[op.top()]){
                       ss.push_back(op.top());
                       op.pop();
                   }
                   now="";
                   now+=s[i];
                   op.push(now);
               }
           }
       }
       if(str!="")  ss.push_back(str);
       while(op.size()){
           ss.push_back(op.top());
           op.pop();
       }
       //后缀表达式求值
       for(int i=0;i<ss.size();i++){
           if(ss[i]=="+"){
               int a=num.top();
               num.pop();
               int b=num.top();
               num.pop();
               num.push(a+b);
           } else if(ss[i]=="-"){
               int a=num.top();
               num.pop();
               int b=num.top();
               num.pop();
               num.push(b-a);
           } else if(ss[i]=="*"){
               int a=num.top();
               num.pop();
               int b=num.top();
               num.pop();
               num.push(a*b);
           } else {
               num.push(stoi(ss[i]));
           }
       }
       //返回表达式的值
       return num.top();
   }
};