题解 | #四则运算#

原思路：

    分三个部分，分别处理括号，乘除，加减。但是处理括号内部信息的时候，设计到乘除和加减的处理，无法解决（PASS）

题解思路：

    简化：

        三个不同的右括号，本质相同表现形式为相对顺序，可以统一为右括号。

    输入：

        使用数据栈和运算栈分别保存数字、运算符

    算法：

        加减与乘除运算的优先级，四则与括号运算的优先级

            总结为先处理乘除与加减的优先级；后处理括号的优先级。

        （1）乘除与加减(可看为无括号时的简化版)，若当前运算的优先级小于等于上个优先级，则处理上个运算；如（3*5-2,3*5*5,3-3-3）

            具体在栈中操作。若栈中的优先级大于等于当前优先级，则pop数据和运算符进行处理。（3-3*5+3）

            好处1：在遇到右括号之前，左括号据当前的元素中，剩下的乘除法只可能在最后，且唯一。

            好处2：从左向右计算，对于（12-5-7+3）不会出现结果为17的错误。

        （2）右括号，遇到右括号时，从双栈中取元素进行计算。

            遍历栈中的元素，若优先级符合且不为'('，执行操作。

            操作后，pop栈首的'('，完成一个括号的内容。

            注意，操作后此时只有一种情况未被处理，即a +- b* / c。

                且乘除仅可能有一个，紧靠右括号会被优先处理。

        （3）遍历字符串时，会有四种情况，左括号，数字，运算符，右括号。

            左括号，压入

            数字，压入，

            运算符，比较优先级并计算，完成没有括号的主要部分。

            右括号，比较栈首优先级并计算，计算完成后pop出'('，完成一个括号的内容

    细节:

        在遍历字符串的4种可能中。根据 数字-运算符-数字顺序 处理，节省编写判别是否数字函数，

            处理数字时，可能存在'-'前缀，以及多位数。

            处理运算符和括号时的运算操作，封装成函数。

                在遍历右括号时，如取元素和运算符执行，直到遇到左括号；执行完成后释放左括号

        优先级比较函数中，除非前+- 后* /，否则返回true。同时，首个运算符前面可能存在'('

        边界条件，到最后i = s.size()时，可能还存在 a + b * c等函数，需要使用while搭配deal_ite进一步处理

    测试用例：

        (7+5*4*3+6), 7+5*4*3+6, 3+2*{1+2*[-4/(8-6)+7]}

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

bool cmp(char &c1, char &c2){

    // 除非前+- 后*/，否则返回true。同时，首个运算符前面可能存在'('
    if(c1 == '(') return false;
    if((c1 == '+' || c1 == '-') && (c2 == '*' || c2 == '/')) return false;
    return true;
}

int deal_op(int &left, char &op, int &right){
    if(op == '+') return left + right;
    if(op == '-') return left - right;
    if(op == '*') return left * right;
    return left / right;
}

void deal_ite(stack<int> &intes, stack<char> &ops){
    int right = intes.top(); intes.pop();
    int left = intes.top(); intes.pop();
    char op = ops.top(); ops.pop();
    int cur = deal_op(left, op, right);
    // cout << cur << endl;
    intes.push(cur);
}

int main(){
    string s;
    cin >> s;

    stack<int> intes;
    stack<char> ops;
    bool isCurOp = false;
    string noNum  = "+-/*()[]{}";   // ([{ 前一般会接运算符，也可不用考虑

    for(int i = 0; i <= s.size(); i++){
        if(i == s.size()) {
            while(!ops.empty() && ops.top() != '(')deal_ite(intes, ops);
            continue;
        }

        // cout << i << " " << s.size() << " " << s[i] << endl;      // printf("i:%d\n", i);     // printf()实时刷新，需要搭配fflust(stdout);
        
        if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
            ops.push('(');  // 统一为'('
        }
        else if(s[i] == ')' || s[i] == ']' || s[i] == '}'){
            // 可能还剩余a-b*c的运算，同时ops中保存有'('
            while(!ops.empty() && ops.top() != '(') {
                deal_ite(intes, ops);
            }
            // 括号内计算完成后，释放左括号
            if(ops.top() == '(') ops.pop();

        }
        else if(isCurOp){
            // 当前为运算符，若当前运算符小于等于前一个运算符（保存在栈中），计算上一个运算符
            while(!ops.empty() && cmp(ops.top(), s[i])){
                deal_ite(intes, ops);
            }
            ops.push(s[i]);
            isCurOp = false;

        }else{
            // 当前为数字。可能存在'-'前缀，以及多位数。
            int j = i;
            if(s[j] == '-') j++;
            while(j < s.size() && noNum.find(s[j]) == noNum.npos) j++;
            intes.push(stoi(s.substr(i, j-i)));
            i  = j - 1;
            isCurOp = true;
        }
    }
    cout << intes.top() << endl;
}