/**
 * LeetCode 772 - Basic Calculator III
 * Evaluates a string expression containing:
 * - Numbers (can be multi-digit)
 * - +, -, *, /
 * - Parentheses
 * - Spaces
 *
 * @param {string} s - The expression to evaluate
 * @return {number} - The result of the expression
 */
function calculate(s) {
  let i = 0;

  // 解析表达式
  function parseExpression() {
    const stack = [];
    let num = 0;
    let sign = '+';

    while (i < s.length) {
      const char = s[i];

      if (char >= '0' && char <= '9') {
        // 解析多位数字
        num = num * 10 + parseInt(char, 10);
      } else if (char === '(') {
        // 遇到左括号，获取整个括号的结果，把整个括号看成一个数
        i++; // Skip the '('
        num = parseExpression(); // 把整个括号里面的内容看成一个表达式，从括号后一个字符开始处理
      } else if (char === ')') {
        // 遇到右括号说明此ParseExpression处理完成，返回整个括号的计算结果给上一个调用
        updateStack(stack, sign, num);
        return calculateStack(stack);
      } else if (char === '+' || char === '-' || char === '*' || char === '/') {
        // 遇到操作需要把处理好的num压入栈中
        updateStack(stack, sign, num);
        sign = char;
        num = 0;
      }

      i++;
    }

    // 将最后一个数字加入栈中
    updateStack(stack, sign, num);

    // 上面的递归解析过程结束之后会得到一个只包含数字的栈，求和即可
    return calculateStack(stack);
  }

  /**
   *
   * @param {number[]} stack 收集数字的栈
   * @param {*} sign - 数字之前的符号
   * @param {*} num - 要处理的数字
   * @description 如果数字的前面是乘除法，就把栈顶元素弹出计算过后作为整体压入栈中；是减法就把这个数改成负数，加法就直接压入栈中
   */
  function updateStack(stack, sign, num) {
    if (sign === '+') {
      stack.push(num);
    } else if (sign === '-') {
      stack.push(-num);
    } else if (sign === '*') {
      stack.push(stack.pop() * num);
    } else if (sign === '/') {
      // 数字前面的操作符如果是除号，需要向下取整
      const prev = stack.pop();
      const result = prev / num;
      stack.push(prev > 0 ? Math.floor(result) : Math.ceil(result));
    }
  }

  // 对整个栈求和
  function calculateStack(stack) {
    return stack.reduce((sum, num) => sum + num, 0);
  }

  return parseExpression();
}

// 测试用例
console.log(calculate('1+1')); // 2
console.log(calculate('6-4/2')); // 4
console.log(calculate('2*(5+5*2)/3+(6/2+8)')); // 21
console.log(calculate('(2+6*3+5-(3*14/7+2)*5)+3')); // -12