224 Basic Calculator 基本計(jì)算器

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-negative integers and empty spaces .

Example:

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.

題目描述:
實(shí)現(xiàn)一個(gè)基本的計(jì)算器來計(jì)算一個(gè)簡單的字符串表達(dá)式的值。

字符串表達(dá)式可以包含左括號 ( ，右括號 )，加號 + ，減號 -，非負(fù)整數(shù)和空格 。

示例 :

示例 1:

輸入: "1 + 1"
輸出: 2

示例 2:

輸入: " 2-1 + 2 "
輸出: 3

示例 3:

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

說明：

你可以假設(shè)所給定的表達(dá)式都是有效的。
請不要使用內(nèi)置的庫函數(shù) eval。

思路:

用棧記錄
因?yàn)檫@里只有加減法運(yùn)算, 可以用一個(gè)符號, 記錄加減符號, 1代表 ‘+’, -1代表 ‘-’
當(dāng)遇到左括號時(shí), 當(dāng)前結(jié)果和符號入棧, 重置結(jié)果和符號
遇到右括號時(shí), 彈出結(jié)果和符號的乘積與之前的結(jié)果求和
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)

代碼:
C++:

class Solution 
{
public:
    int calculate(string s) 
    {
        vector<int> record;
        int sign = 1, result = 0, n = s.size();
        for (int i = 0; i < n; i++) 
        {
            auto c = s[i];
            if (isdigit(c)) 
            {
                auto cur = c - '0';
                while (i < n - 1 and isdigit(s[i + 1])) cur = 10 * cur + (s[++i] - '0');
                result += sign * cur;
            } 
            else if (c == '+') sign = 1;
            else if (c == '-') sign = -1;
            else if (c == '(') 
            {
                record.push_back(result);
                result = 0;
                record.push_back(sign);
                sign = 1;
            } 
            else if (c == ')') 
            {
                result *= record.back();
                record.pop_back();
                result += record.back(); 
                record.pop_back();
            }
        }
        return result;
    }
};

Java:

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int sign = 1, result = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int cur = c - '0';
                while (i < n - 1 && Character.isDigit(s.charAt(i + 1))) cur = 10 * cur + s.charAt(++i) - '0';
                result += sign * cur;
            } else if (c == '+') sign = 1;
            else if (c == '-') sign = -1;
            else if (c == '(') {
                stack.push(result);
                result = 0;
                stack.push(sign);
                sign = 1;
            } else if (c == ')') result = stack.pop() * result + stack.pop(); 
        }
        return result;
    }
}

Python:

class Solution:
    def calculate(self, s: str) -> int:
        stack, sign, result, n, i = [], 1, 0, len(s), 0
        while i < n:
            c = s[i]
            if c.isnumeric():
                cur = int(c)
                while i < n - 1 and s[i + 1].isnumeric():
                    cur *= 10
                    i += 1
                    cur += int(s[i])
                result += sign * cur
            elif c == '+':
                sign = 1
            elif c == '-':
                sign = -1
            elif c == '(':
                stack.append(result)
                result = 0
                stack.append(sign)
                sign = 1
            elif c == ')':
                result = stack.pop() * result + stack.pop()
            i += 1
        return result