题目描述

> 输入一个表达式（用字符串表示），求这个表达式的值。 保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

思路参考：https://leetcode-cn.com/problems/basic-calculator-ii/solution/shi-yong-shuang-zhan-jie-jue-jiu-ji-biao-c65k/

这是一道简单题？？？ 1、将所有的括号都换成小括号； 2、设置符号栈和数字栈 3、设置函数cal()，对数字栈栈顶的两个元素和符号栈栈顶的一个元素进行运算（注意顺序） 输入遇到前括号- push入符号栈；判断下一位如果是也是符号，则先往数字栈中push一个0； 输入遇到后括号- 直到遇到前括号前，一直进行cal()计算，算出括号内的答案后push入数字栈；此时括号内栈从下往上看优先级是递增的，直接按出栈顺序直接计算后入栈。 输入遇到数字- 向后判断这个数字有多长，截取字符串转换成数字放入数字栈； 输入遇到+-*/符号- 判断该符号与符号栈栈顶符号的优先级，当小于等于的时候进行cal，然后再入栈，否则直接入符号栈。小于是当出现先乘除后加减的情况，等于表示同级运算，应该从左向右，所以先计算栈里的。注意这里是while循环。 4、最后结束循环化，对栈再进行一次while的cal()，输出最后留下的唯一的栈顶。 5、但凡需要循环，判断条件都要注意此时是否是空栈。

#include<iostream>
#include<vector>
#include<stack>
#include <string>
#include <map>
using namespace std;
bool isdigital(char a) {
    return ('0' &lt;= a &amp;&amp; a &lt;= '9') ? true : false;
}
void cal(stack<int>&amp; num, stack<char>&amp; symbol) {//取出数字栈顶的两个元素和符号栈顶的一个符号进行运算
    int a = num.top();
    num.pop();
    int b = num.top();
    num.pop();
    char c = symbol.top();
    symbol.pop();
    int ans;
    switch (c) {//一定要注意是b对a操作
    case '+': {ans = b + a; break; }
    case '-': {ans = b - a; break; }
    case '*': {ans = b * a; break; }
    case '/': {ans = b / a; break; }
    }
    num.push(ans);//计算结果放回栈中

}
int main() {
    string s;
    cin &gt;&gt; s;
    map<char, int> grade;
    grade['('] = 0; grade[')'] = 0; grade['+'] = 1; grade['-'] = 1; grade['*'] = 2; grade['/'] = 2;
    for (int i = 0; i &lt; s.length(); i++) {
        if (s[i] == '{' || s[i] == '[') s[i] = '(';
        if (s[i] == '}' || s[i] == ']') s[i] = ')';
    }
    stack<int> num;
    stack<char> symbol;
    if (!isdigital(s[0])) num.push(0);//避免-5*4这种上来就是符号的
    for (int i = 0; i &lt; s.length(); i++) {
        if (s[i] == '(') {//如果是左括号，入符号栈
            symbol.push('(');
            if (!isdigital(s[i + 1]))//避免(-4+5)这样的情况出现，所以入0
                num.push(0);
        }
        else if (s[i] == ')') {//遇到后括号，则将该括号内式子计算出来
            while (symbol.top() != '(')
                cal(num, symbol);//计算括号里的
            symbol.pop();//左括号弹出
        }
        else if (isdigital(s[i])) {//遇到数字，提取出完整的数字放入数字栈
            int left = i;
            while (i + 1 &lt; s.length() &amp;&amp; isdigital(s[i + 1])) i++;
            num.push(stoi(s.substr(left, i - left + 1)));//也可以ans=ans*10+s[i]算出来
        }
        else //如果是+-*/，当s[i]的优先级小于等于栈顶符号优先级时，对栈顶进行一次计算，直到不符合条件
        {
            while (!symbol.empty() &amp;&amp; grade[s[i]] &lt;= grade[symbol.top()])//注意这里是while不是if，如9-5*4+5;
                cal(num, symbol);
            symbol.push(s[i]);
        }
    }
    while (!symbol.empty())
        cal(num, symbol);
    cout &lt;&lt; num.top();
}
```</char></int></char,></char></int></map></string></stack></vector></iostream>