Basic Calculator

https://leetcode.com/problems/basic-calculator/description/

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open(and closing parentheses), the plus+or minus sign-,non-negativeintegers and empty spaces.

You may assume that the given expression is always valid.

Thoughts

eval由+-()组成的数学数学表达式。nested括号匹配是stack最常见的应用之一。栈里存(之前计算出的结果并记录(对应的正负号，栈外存当前的结果。遇到)就把s内一个结果pop出并和当前结果合并成新的当前结果。

Code

/*
 * @lc app=leetcode id=224 lang=cpp
 *
 * [224] Basic Calculator
 */
class Solution {
public:
    int calculate(string str) {
        int num = 0, sign = 1, res = 0;
        stack<int> s;
        for (const auto c : str) {
            if (c >= '0' && c <= '9') num = num * 10 + (c - '0');
            else if (c == '+') {
                res += sign * num;
                sign = 1;
                num = 0;
            } else if (c == '-') {
                res += sign * num;
                sign = -1;
                num = 0;
            } else if (c == '(') {
                s.push(res);
                s.push(sign);
                sign = 1;
                num = 0;
                res = 0;
            } else if (c == ')') {
                int psign = s.top(); s.pop();
                int pres = s.top(); s.pop();
                res += sign * num;
                res *= psign;
                res += pres; 
                num = 0;
                sign = 1;
            }
        }
        if (num != 0) res += sign * num;
        return res;
    }
};

Analysis

Errors:

1. 忘了把num, res, sigh等重置

2. 右括号时忘了写res += sign * num;

时空复杂度都是O(N).