本文共 2317 字，大约阅读时间需要 7 分钟。

输入

复制 “(2*(3-4))*5” 返回值 复制 -10

算法思路

1.用栈保存各部分计算的和

2.遍历表达式 3.遇到数字时继续遍历求这个完整的数字的值 4.遇到左括号时递归求这个括号里面的表达式的值 5.遇到运算符时或者到表达式末尾时，就去计算上一个运算符并把计算结果push进栈，然后保存新的运算符 如果是+，不要计算，push进去 如果是-，push进去负的当前数 如果是×、÷，pop出一个运算数和当前数作计算 6.最后把栈中的结果求和即可

class Solution {
       stack
   
     num;    stack
    
      sig;    int com(int a,int b,char x) {
           if (x=='+') return a+b;        if (x=='*') return a*b;        if (x=='-') return a-b;        if (x == '/' && b) return a/b;        return -9999999;    }    void calc() {
           int b = num.top();  num.pop();        int a = num.top();  num.pop();        char op = sig.top();sig.pop();        num.push (com(a,b,op));                    }    void changes(string s) {
           for (int i=0;i
     
      0 && s[i-1] == '(') s.insert(i,"0");            }        }        return;    }            public:    /**     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可     * 返回表达式的值     * @param s string字符串 待计算的表达式     * @return int整型     */    int solve(string s) {
           // write code here        if (s.empty()) return -1;        changes(s);        for (int i=0;i
      
       ='0' && e<='9' && i
       
        ='0' && j<=s.size()) {
                       temp = temp*10 +(s[j]-'0');                    ++j;                }                num.push(temp);                i = j-1;                            }else  {
                   char e = s[i];                if (e=='(' || sig.empty()) {
                       sig.push(e);                }                else{
                       if (s[i] =='+' || s[i] == '-') {
                           while (sig.size() && sig.top()!='('){
                               calc();                        }                        sig.push(s[i]);                    }                    if (s[i]=='*' || s[i] =='/') {
                           // 要和栈前面的进行计算                        while(sig.size() && (sig.top()=='*'||sig.top()=='/')) calc();                        sig.push(s[i]);                    }                    if (s[i] ==')') {
                           while (sig.size() && sig.top() !='(' ){
                               calc();                        }                        sig.pop();                    }                }            }        }        while (sig.size()) calc();        return num.top();            }};
       
      
     
    
   

转载地址：http://ouyzi.baihongyu.com/