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

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.

Solution(javascript)

/**  括号会影响运算顺序, 不能直接去括号
 * @param {string} s
 * @return {number}
 */
const calculate = function (s) {
  const help = xs => xs.reduce((acc, item, index) => {
    if (item === '-') {
      xs[index + 1] = -xs[index + 1]
      return acc
    } if (item === '+') {
      return acc
    }
    return acc + item
  }, 0)

  const stack = []
  let current = ''
  for (const c of s) {
    // 去空格，组合数字
    if (c === '-' || c === '+' || c === '(' || c === ')') {
      if (current !== '') {
        stack.push(parseInt(current, 10))
        current = ''
      }
      stack.push(c)
    } else if (c === ' ') {
      if (current !== '') {
        stack.push(parseInt(current, 10))
        current = ''
      }
    } else {
      current += c
    }

    // 去括号
    while (stack[stack.length - 1] === ')') {
      stack.pop()
      const temp = []
      while (stack[stack.length - 1] !== '(') {
        temp.push(stack.pop())
      }
      stack.pop()
      stack.push(
        help(temp.reverse()),
      )
    }
    // console.log(c, stack)
  }
  if (current !== '') {
    stack.push(parseInt(current, 10))
  }
  return help(stack)
}