Evaluate a Basic Arithmetic Expression

hard stack parsing

Problem

Given a string with non-negative integers, +, -, parentheses, and spaces, return its integer value. Walk left-to-right keeping a running result and a current sign (+1 or -1). On a digit, parse the full number and apply the sign. On +/-, set the next sign. On (, push the current result and sign and reset; on ), multiply the inner result by the saved sign and add it to the saved outer result.

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

Output23

Inner blocks evaluate to 8 and 14; (1+8-3) + 14 = 23.

expression

def calculate(s):
    result, sign, i = 0, 1, 0
    stack = []
    while i < len(s):
        c = s[i]
        if c == " ":
            i += 1; continue
        if c.isdigit():
            n = 0
            while i < len(s) and s[i].isdigit():
                n = n * 10 + int(s[i]); i += 1
            result += sign * n
            continue
        if c == "+": sign = 1
        elif c == "-": sign = -1
        elif c == "(":
            stack.append(result); stack.append(sign)
            result, sign = 0, 1
        elif c == ")":
            result = stack.pop() * result + stack.pop()
        i += 1
    return result

function calculate(s) {
  let result = 0, sign = 1, i = 0;
  const stack = [];
  while (i < s.length) {
    const c = s[i];
    if (c === " ") { i++; continue; }
    if (c >= "0" && c <= "9") {
      let n = 0;
      while (i < s.length && s[i] >= "0" && s[i] <= "9") { n = n * 10 + (s.charCodeAt(i) - 48); i++; }
      result += sign * n;
      continue;
    }
    if (c === "+") { sign = 1; }
    else if (c === "-") { sign = -1; }
    else if (c === "(") { stack.push(result); stack.push(sign); result = 0; sign = 1; }
    else if (c === ")") { result = stack.pop() * result + stack.pop(); }
    i++;
  }
  return result;
}

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

int calculate(string s) {
    int result = 0, sign = 1, i = 0;
    vector<int> stack;
    while (i < (int)s.size()) {
        char c = s[i];
        if (c == ' ') { ++i; continue; }
        if (isdigit(c)) {
            int n = 0;
            while (i < (int)s.size() && isdigit(s[i])) { n = n * 10 + (s[i] - '0'); ++i; }
            result += sign * n;
            continue;
        }
        if (c == '+') sign = 1;
        else if (c == '-') sign = -1;
        else if (c == '(') { stack.push_back(result); stack.push_back(sign); result = 0; sign = 1; }
        else if (c == ')') { int sg = stack.back(); stack.pop_back(); int prev = stack.back(); stack.pop_back(); result = sg * result + prev; }
        ++i;
    }
    return result;
}

Time: O(n) Space: O(n)