题解 | #四则运算#

#include <cctype>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

double dealWithOperator(double a, double b, char c) {
    if (c == '+')
        return a + b;
    else if (c == '-')
        return a - b;
    else if (c == '*')
        return a * b;
    else if (c == '/')
        return a / b;
    return 0;
}

int priority(char c) {
    if (c == '+' || c == '-')
        return 1;
    else if (c == '*' || c == '/')
        return 2;
    else if (c == '(')
        return 3;
    return -1;
}


double stringExpression2result(string& s) {
    for (char& i : s) {
        if (i == '{' || i == '[')
            i = '(';
        else if (i == '}' || i == ']')
            i = ')';
    }


    stack<char> os;
    stack<string> num;
    //利用string来储存数值也是一个好思路
    //经典算法，双栈法，利用两个栈，一个用于处理操作数，一个用于处理预算符号
    double out = 0;
    for (int i = 0; i != s.size(); ++i) {
        if (s[i] == ' ')
            continue;
        if (isdigit(s[i])) {
            string number;
            while (i != s.size() && isdigit(s[i])) {
                number += s[i];
                ++i;
            }
            --i;//上一步额外的加了一次
            num.push(number);
        }
        else if (s[i] == '(') {
            //遇到左括号(进行压栈
            os.push(s[i]);
        }
        else if (s[i] == ')') {
            while (!os.empty() && os.top() != '(') {
                //处理括号内的内容
                double num1 = stod(num.top());
                num.pop();
                double num2 = stod(num.top());
                num.pop();
                char op = os.top();
                os.pop();
                num2 = dealWithOperator(num2, num1, op);
                num.push(to_string(num2));
            }
            if (!os.empty())
                //弹出'('
                os.pop();
        }
        else {
            //如何处理运算符
            if (s[i] == '-') {
                if (isdigit(s[i + 1]) && (i == 0 || s[i - 1] == '(')) {
                    string k(1, '-');
                    k += s[i + 1];
                    num.push(k);
                    i++;
                    continue;
                }
            }
            if (!os.empty()) {
                int pot = priority(os.top());
                int pon = priority(s[i]);

                if (pot >= pon && pot != 3) {
                    // dirctly compute
                    double n1 = stod(num.top());
                    num.pop();
                    double n2 = 0;
                    // if there isn't a second number in num
                    // might be the first number is a negative number
                    if (!num.empty()) {
                        n2 = stod(num.top());
                        num.pop();
                    }
                    char op = os.top();
                    os.pop();
                    if (!os.empty() && os.top() == '-' && op == '-')
                    {
                        n2 = dealWithOperator(n2, n1, '+');
                        num.push(to_string(n2));
                    }
                    else
                    {
                        n2 = dealWithOperator(n2, n1, op);
                        num.push(to_string(n2));
                    }
                }

            }
            os.push(s[i]);
        }
    }
    while (!os.empty()) {
        double num1 = stod(num.top());
        num.pop();
        double num2 = stod(num.top());
        num.pop();
        char op = os.top();
        os.pop();
        num2 = dealWithOperator(num2, num1, op);
        num.push(to_string(num2));
    }
    out = stod(num.top());
    return out;
}

int main() {
    string s;
    getline(cin, s);
    cout << stringExpression2result(s);
}
// 64 位输出请用 printf("%lld")

这个题的核心在于要利用FILO的stack操作，因为有括号的存在，每次遇到")"就要从后往前一直推到"("为止，利用双栈法，一个储存数字，一个储存符号，但是值得注意的是两个，一个-n或者(-n的负数情况，另一个是-6-3+2的时候按照堆栈的做法是6-3，这样是错误的，需要额外一个判断