题目描述

> 输入一个表达式(用字符串表示),求这个表达式的值。 保证字符串中的有效字符包括[‘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>