题目

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。

示例 1:

输入: "1 + 1"
输出: 2
示例 2:

输入: " 2-1 + 2 "
输出: 3
示例 3:

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

C++解法

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
class Solution {
public:
    bool isNumber(char c) { return c >= 48 && c <= 57; }
    
    int evaluate(string & numberString)  {
        int value = 0;
        for (char digit: numberString) {
            value *= 10;
            value += digit - '0';
        }
        numberString.clear();
        return value;
    }
    
    int evaluate(vector<char> & operatorStack, vector<int> & operandStack) {
        int result = operandStack[0];
        for (int i = 0; i < operatorStack.size(); i++) {
            if (operatorStack[i] == '+') result += operandStack[i + 1];
            else if (operatorStack[i] == '-') result -= operandStack[i + 1];
        }
        operatorStack.clear();
        operandStack.clear();
        return result;
    }
    
    int calculate(string s) {
        bool isEvaluating = false;
        int depth = 0, maxDepth = 0;
        string prevString = "", nextString = "", numberString = "";
        vector<int> operands = {};
        vector<char> operators = {};
        for (auto c: s) {
            if (isNumber(c) || c == '+' || c == '-' || c == '(' || c == ')') prevString.push_back(c);
        }
        do {
            maxDepth = 0;
            depth = 0;
            numberString.clear();
            int value = 0;
            for (char c: prevString) {
                if (c == '(') {
                    ++depth;
                } else if (c == ')') {
                    if (depth > maxDepth) maxDepth = depth;
                    --depth;
                }
            }
            depth = 0;
            isEvaluating = false;
            for (int i = 0; i < prevString.size(); ++i) {
                char c = prevString[i];
                if (c == '(') {
                    ++depth;
                    if (depth == maxDepth) {
                        isEvaluating = true;
                    } else {
                        nextString.push_back(c);
                    }
                } else if (c == ')') {
                    if (isEvaluating) {
                        if (!numberString.empty()) {
                            value = evaluate(numberString);
                            operands.push_back(value);
                        }
                        int result = evaluate(operators, operands);
                        if (nextString.empty()) {
                            return result;
                        } else {
                            if (result >= 0) {
                                 nextString.append(to_string(result));
                             } else {
                                 if (nextString[nextString.size() - 1] == '+') {
                                     nextString[nextString.size() - 1] = '-';
                                 } else if (nextString[nextString.size() - 1] == '-') {
                                     nextString[nextString.size() - 1] = '+';
                                 }
                                 nextString.append(to_string(abs(result)));
                             }
                        }
                        isEvaluating = false;
                    } else {
                        nextString.push_back(c);
                    }
                    --depth;
                } else {
                    if (isEvaluating || maxDepth == 0) {
                        if (c == '+' || c == '-') {
                            operators.push_back(c);
                        } else if (isNumber(c)) {
                            numberString.push_back(c);
                        }
                        if (i == prevString.size() - 1 || !isNumber(c)) {
                            if (!numberString.empty()) {
                                value = evaluate(numberString);
                                operands.push_back(value);
                            }
                        }
                    } else {
                        nextString.push_back(c);
                    }
                }
            }
            prevString = nextString;
            nextString = "";
        } while (maxDepth > 0);
        return evaluate(operators, operands);
    }
};

int main(int argc, const char * argv[]) {
    // insert code here...
    Solution solution;
    cout << solution.calculate("1 + 2") << endl;
    cout << solution.calculate("2 - 1 + 2") << endl;
    cout << solution.calculate("1 + 1") << endl;
    cout << solution.calculate("2 - (5 - 6)") << endl;
    cout << solution.calculate("(1+(4+5+2)-3)+(6+8)") << endl;
    cout << solution.calculate("(5-1)") << endl;
    cout << solution.calculate("(5-(1+(5)))") << endl;
    cout << solution.calculate("(1-5)") << endl;
    cout << solution.calculate("2 - 1 + 2") << endl;
    cout << solution.calculate("(1 + ((2 + 3) * (4 * 5)))") << endl;
    cout << solution.calculate("((1+(((4+5)+2)-3))+(6+8))") << endl;
    return 0;
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator