/**
 * 將純數(shù)字字符串轉(zhuǎn)為整數(shù)（如 "123" → 123）
 * @param {string} str - 僅包含數(shù)字字符的字符串
 * @returns {number} 轉(zhuǎn)換后的整數(shù)
 */
function stringToInt(str) {
  let num = 0; // 累加結(jié)果，初始為 0（乘法的單位元，不影響首次 num*10+cur）
  let i = 0; // 當(dāng)前掃描到的下標(biāo)
  // 只要未越界且當(dāng)前字符是數(shù)字，就繼續(xù)讀（多位數(shù)一次性讀完）
  while (i < str.length && /[0-9]/.test(str[i])) {
    num = num * 10 + (str[i] - '0'); // 左移一位（×10）+ 當(dāng)前位數(shù)字；'5'-'0' → 5
    i++;
  }
  return num;
}

/**
 * 只支持 +、-、數(shù)字、空格的表達(dá)式（減法轉(zhuǎn)為加負(fù)數(shù)，最后統(tǒng)一求和）
 * @param {string} s - 表達(dá)式字符串，如 "1 - 12 + 3"
 * @returns {number} 計(jì)算結(jié)果
 */
function calculateAddSub(s) {
  const stack = []; // 存「帶符號(hào)的加數(shù)」，最后全部相加即可
  let sign = '+'; // 當(dāng)前數(shù)字前的符號(hào)，第一個(gè)數(shù)字前默認(rèn)為 +
  const n = s.length;

  for (let i = 0; i < n; i++) {
    const c = s[i];
    if (c === ' ') continue; // 空格跳過(guò)，避免被誤判為數(shù)字

    // 遇到數(shù)字：用 while 一次性讀完多位數(shù)
    if (/[0-9]/.test(c)) {
      let num = 0;
      while (i < n && /[0-9]/.test(s[i])) {
        num = num * 10 + (s[i] - '0');
        i++;
      }
      stack.push(sign === '+' ? num : -num); // 按當(dāng)前符號(hào)入棧（減法即存負(fù)數(shù)）
      i--; // while 結(jié)束時(shí) i 已指向非數(shù)字，for 會(huì)再 i++，故回退一步避免跳過(guò)
      continue;
    }

    // 遇到 + 或 -：只更新符號(hào)，下一個(gè)數(shù)字將使用該符號(hào)入棧
    if (c === '+' || c === '-') {
      sign = c;
    }
  }

  // 棧內(nèi)全是帶符號(hào)的加數(shù)，直接求和
  let sum = 0;
  while (stack.length) sum += stack.pop();
  return sum;
}

/**
 * 根據(jù)「數(shù)字前的運(yùn)算符」把 num 入棧（加減存帶符號(hào)數(shù)，乘除與棧頂算完再入棧）
 * @param {number[]} stack - 數(shù)字棧
 * @param {string} signBeforeNum - 該數(shù)字前的運(yùn)算符（+、-、*、/）
 * @param {number} num - 剛讀完的數(shù)字
 */
function addNumToStack(stack, signBeforeNum, num) {
  switch (signBeforeNum) {
    case '+':
      stack.push(num); // 加：直接入棧
      break;
    case '-':
      stack.push(-num); // 減：轉(zhuǎn)成加負(fù)數(shù)入棧
      break;
    case '*':
      stack.push(stack.pop() * num); // 乘：彈出棧頂 × 當(dāng)前數(shù)，結(jié)果入棧（乘除優(yōu)先）
      break;
    case '/':
      const top = stack.pop();
      stack.push(Math.trunc(top / num)); // 除：向零取整，如 -5/2 → -2
      break;
  }
}

/**
 * 支持 +、-、*、/、數(shù)字、空格，乘除優(yōu)先于加減
 * @param {string} s - 表達(dá)式，如 "10 - 2*3 + 8/2"
 * @returns {number} 計(jì)算結(jié)果
 */
function calculateMulDiv(s) {
  const stack = []; // 存待累加的項(xiàng)（加減已轉(zhuǎn)符號(hào)，乘除已算完）
  let signBeforeNum = '+'; // 「下一個(gè)數(shù)字」前的運(yùn)算符，第一個(gè)數(shù)字前默認(rèn)為 +
  const n = s.length;

  for (let i = 0; i < n; i++) {
    const c = s[i];
    if (c === ' ') continue;

    // 遇到數(shù)字：while 讀完多位數(shù)，再按 signBeforeNum 入棧
    if (/[0-9]/.test(c)) {
      let num = 0;
      while (i < n && /[0-9]/.test(s[i])) {
        num = num * 10 + (s[i] - '0');
        i++;
      }
      addNumToStack(stack, signBeforeNum, num);
      i--;
      continue;
    }

    // 遇到運(yùn)算符：只更新「下一個(gè)數(shù)字前的符號(hào)」，數(shù)字入棧在讀完數(shù)字時(shí)由 addNumToStack 完成
    if (['+', '-', '*', '/'].includes(c)) {
      signBeforeNum = c;
    }
  }

  return stack.reduce((a, b) => a + b, 0);
}

/**
 * 建立括號(hào)配對(duì)：左括號(hào)下標(biāo) → 對(duì)應(yīng)的右括號(hào)下標(biāo)（嵌套括號(hào)用棧就近匹配）
 * @param {string} s - 表達(dá)式字符串
 * @returns {Map<number, number>} 左括號(hào)索引 → 右括號(hào)索引
 */
function getBracketMap(s) {
  const map = new Map();
  const stack = []; // 存左括號(hào)的下標(biāo)，遇到 ) 時(shí)彈棧即得到與之匹配的 (
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i); // 左括號(hào)：記錄其下標(biāo)，等待匹配
    }
    if (s[i] === ')') {
      const left = stack.pop(); // 彈出最近的左括號(hào)下標(biāo)，即與當(dāng)前 ) 配對(duì)
      map.set(left, i); // 記錄配對(duì)關(guān)系
    }
  }
  return map;
}

/**
 * 表達(dá)式計(jì)算函數(shù)（支持 +-*\/、數(shù)字、空格、嵌套括號(hào)，遵循 括號(hào)>乘除>加減 優(yōu)先級(jí)）
 * @param {string} s - 輸入表達(dá)式，示例："1+2+1*3+(3*6+12*(3+3))-5"
 * @returns {number} - 計(jì)算結(jié)果
 *
 * 核心設(shè)計(jì)思路：
 * 1. 棧的作用：存儲(chǔ)待累加的數(shù)字（根據(jù)符號(hào)決定數(shù)字進(jìn)棧的值，加減轉(zhuǎn)符號(hào)存儲(chǔ)，乘除優(yōu)先計(jì)算后存儲(chǔ)，括號(hào)結(jié)果作為單個(gè)數(shù)字存儲(chǔ)）
 * 2. 符號(hào)規(guī)則：signBeforeNum 記錄「當(dāng)前數(shù)字的前一個(gè)運(yùn)算符」，決定數(shù)字如何入棧
 * 3. 字符處理優(yōu)先級(jí)：空格跳過(guò) → 數(shù)字拼接 → 左括號(hào)遞歸 → 運(yùn)算符更新符號(hào)
 */
function calculate(s) {
  const stack = []; // 存儲(chǔ)待累加的數(shù)字棧（核心數(shù)據(jù)結(jié)構(gòu)）
  const bracketMap = getBracketMap(s); // 預(yù)生成「左括號(hào)索引→右括號(hào)索引」映射，解決嵌套括號(hào)匹配
  let signBeforeNum = '+'; // 【易錯(cuò)點(diǎn)1】初始值必須為+，對(duì)應(yīng)第一個(gè)數(shù)字前默認(rèn)是加號(hào)

  // 遍歷表達(dá)式的每個(gè)字符
  for (let i = 0; i < s.length; i++) {
    let curChar = s[i];

    // 1. 跳過(guò)空格（唯一需要主動(dòng)跳過(guò)的特殊字符）
    if (curChar === ' ') continue;

    // 2. 處理連續(xù)數(shù)字拼接（核心邏輯：多位數(shù)拆解）
    if (/[0-9]/.test(curChar)) {
      let num = 0;
      // 循環(huán)拼接所有連續(xù)數(shù)字，直到遇到非數(shù)字字符
      while (i < s.length && /[0-9]/.test(s[i])) {
        // 【易錯(cuò)點(diǎn)2】必須加i < s.length，避免越界
        // 【易錯(cuò)點(diǎn)3】必須用s[i]而非curChar，curChar是循環(huán)外的初始值，不會(huì)隨i更新
        const singleNum = s[i] - '0';
        num = num * 10 + singleNum; // 位權(quán)原理拼接多位數(shù)（如1→12→123）
        i++; // 移動(dòng)到下一個(gè)字符
      }
      // 數(shù)字拼接完成，按符號(hào)入棧
      addNumToStack(stack, num, signBeforeNum);
      // 【易錯(cuò)點(diǎn)4】核心細(xì)節(jié)：循環(huán)后i指向非數(shù)字，外層i++會(huì)跳過(guò)運(yùn)算符，必須回退一步
      i--;
      continue; // 跳過(guò)后續(xù)邏輯，避免數(shù)字被誤判為運(yùn)算符
    }

    // 3. 處理左括號(hào)（遞歸+索引跳轉(zhuǎn)，無(wú)需處理右括號(hào)）
    if (curChar === '(') {
      const rightBracketIdx = bracketMap.get(i); // 獲取匹配的右括號(hào)索引
      // 【易錯(cuò)點(diǎn)5】遞歸截取范圍是[i+1, rightBracketIdx)，不包含右括號(hào)
      const bracketRes = calculate(s.slice(i + 1, rightBracketIdx));
      // 括號(hào)結(jié)果作為單個(gè)數(shù)字，按當(dāng)前符號(hào)入棧
      addNumToStack(stack, bracketRes, signBeforeNum);
      // 【易錯(cuò)點(diǎn)6】跳到右括號(hào)索引，外層i++會(huì)自然跳過(guò)右括號(hào)，無(wú)需額外處理)
      i = rightBracketIdx;
      continue; // 本次循環(huán)結(jié)束，避免后續(xù)邏輯處理右括號(hào)
    }

    // 4. 處理運(yùn)算符（僅更新符號(hào)，數(shù)字入棧邏輯在數(shù)字拼接時(shí)觸發(fā)）
    if (['+', '-', '*', '/'].includes(curChar)) {
      // 【易錯(cuò)點(diǎn)7】符號(hào)僅記錄，不立即計(jì)算，作用于下一個(gè)數(shù)字
      signBeforeNum = curChar;
    }
  }

  // 5. 棧內(nèi)所有數(shù)字累加（加減已轉(zhuǎn)符號(hào)，乘除/括號(hào)已計(jì)算，直接求和）
  let sum = 0;
  while (stack.length) {
    sum += stack.pop();
  }
  return sum;
}

/**
 * 建立括號(hào)配對(duì)：左括號(hào)下標(biāo) → 右括號(hào)下標(biāo)（僅掃一遍，嵌套用棧匹配）
 */
function getBracketMap(s) {
  const map = new Map();
  const stack = []; // 存左括號(hào)下標(biāo)
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') stack.push(i);
    if (s[i] === ')') map.set(stack.pop(), i);
  }
  return map;
}

/**
 * 按「數(shù)字前的運(yùn)算符」將 num 入棧：加減存帶符號(hào)數(shù)，乘除與棧頂算完再入棧
 */
function addNumToStack(stack, signBeforeNum, num) {
  switch (signBeforeNum) {
    case '+':
      stack.push(num);
      break;
    case '-':
      stack.push(-num);
      break;
    case '*':
      stack.push(stack.pop() * num);
      break;
    case '/':
      stack.push(Math.trunc(stack.pop() / num));
      break;
  }
}

/**
 * 表達(dá)式計(jì)算（優(yōu)化版：不復(fù)制 s，只傳區(qū)間；bracketMap 只算一次）
 * @param {string} s - 整段表達(dá)式
 * @returns {number} 計(jì)算結(jié)果
 */
function calculate(s) {
  const bracketMap = getBracketMap(s); // 整串只算一次，遞歸過(guò)程中通過(guò)閉包共用
  return calc(0, s.length - 1);

  /** 只處理 s[low..high] 這一段，不復(fù)制字符串 */
  function calc(low, high) {
    const stack = [];
    let signBeforeNum = '+';

    for (let i = low; i <= high; i++) {
      const c = s[i];
      if (c === ' ') continue;

      // 數(shù)字：while 讀完多位數(shù)（注意邊界 i <= high），入棧后 i-- 避免 for 多跳一格
      if (/[0-9]/.test(c)) {
        let num = 0;
        while (i <= high && /[0-9]/.test(s[i])) {
          num = num * 10 + (s[i] - '0');
          i++;
        }
        addNumToStack(stack, signBeforeNum, num);
        i--;
        continue;
      }

      // 左括號(hào)：用預(yù)算好的 bracketMap 取匹配的右括號(hào)，遞歸區(qū)間 [i+1, right-1]，結(jié)果入棧后跳過(guò)整段
      if (c === '(') {
        const right = bracketMap.get(i);
        const sub = calc(i + 1, right - 1);
        addNumToStack(stack, signBeforeNum, sub);
        i = right;
        continue;
      }

      // 運(yùn)算符：更新「下一個(gè)數(shù)字前的符號(hào)」
      if (['+', '-', '*', '/'].includes(c)) {
        signBeforeNum = c;
      }
    }

    return stack.reduce((a, b) => a + b, 0);
  }
}