[数据结构与算法]HJ54 表达式求值（c++）

题目链接：表达式求值_牛客题霸_牛客网

注意点：(中缀表达式直接求值)

1.双栈计算，数字栈si，符号栈sc

2.?遇到数字要区分正负号和加减号，可以用一个flag标记每轮是否出现过了数字了，数字之前的为正负号，数字之后的为加减号。

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;

//运算符优先级比较，括号优先级最高，然后是乘除，再加减
bool priority(const char &a,const char &b){
    if(a == '(') return false;
    if(((a == '+')||(a == '-'))&&((b == '*')||(b == '/')))
        return false;
    return true;
}
//根据栈顶运算符弹出两个元素进行运算,并把结果压入数字栈顶
void compute(stack<int> &si,stack<char> &sc){
    int b = si.top();
    si.pop();
    int a = si.top();
    si.pop();
    //运算符栈顶
    char op = sc.top();
    sc.pop();
    if(op == '+') a = a + b;
    else if(op == '-') a = a - b;
    else if(op == '*') a = a * b;
    else if(op =='/') a = a / b;
    //计算结果压入数字栈顶
    si.push(a);
}

int main() {
    string str;
    while(getline(cin,str)){
        stack<int> si;
        stack<char> sc;
        //给整个表达式加上()
        str = "("+str+")";
        bool flag = false;
        for(int i = 0;i < str.size(); ++i){
            //遇到左括号假如到运算栈
            if(str[i]=='('){
                sc.push('(');
            }
            //遇到右括号
            else if(str[i] == ')'){
                //弹出开始计算，直到遇到左括号
                while(sc.top() != '('){
                    compute(si,sc);
                }
                //弹出左括号
                sc.pop();
            }
            //运算符比较优先级
            else if (flag){
                while(priority(sc.top(),str[i])){
                    compute(si,sc);
                }
                //现阶段符号入栈等待下次计算
                sc.push(str[i]);
                flag = false;
            }
            //数字
            else{
                //开始记录
                int j = i;
                //正负号
                if(str[j] == '+'||str[j] == '-') i++;
                while(isdigit(str[i])){
                    i++;
                }
                //截取数字部分
                string temp = str.substr(j,i - j);
                si.push(stoi(temp));
                //注意外层i还会+1,所以这里-1
                i--;
                //数字完了肯定是符号
                flag = true;
            }
        }
        //最后的数字栈剩个结果，符号栈都为空。
        cout<<si.top()<<endl;
    }
}