表达式计算

// 符号优先级
const precedence = {
  "+": 1,
  "-": 1,
  "*": 2,
  "/": 2,
  "(": 0,
} as const;

function mathEval(expr: string): number {
  const tokens = expr.replace(/\s+/g, "").match(/(\d+(?:\.\d+)?|\*\*|[-+*/()!])/g) || [];
  const operands: number[] = [];
  const operators: string[] = [];
  // 记录上一个 token 的类型：数字 | 运算符 | '(' | 空
  let prevTokenType: "number" | "operator" | "parenOpen" | "none" = "none";
  // 处理负号
  let sign = 1;

  for (const token of tokens) {
    // 如果是数字，数字入栈
    if (/\d+/.test(token)) {
      operands.push(sign * parseFloat(token));
      sign = 1;
      prevTokenType = "number";
    }
    // 如果是 '('，符号入栈
    else if (token === "(") {
      operators.push(token);
      prevTokenType = "parenOpen";
    }
    // 如果是 ')'，符号出栈，直到 '('
    else if (token === ")") {
      while (operators.length > 0 && operators[operators.length - 1] !== "(") {
        applyTopOperator(operands, operators);
      }
      operators.pop(); // 移除 '('
      prevTokenType = "number"; // ')' 后视为数字
    }
    // 如果是运算符
    else {
      // 处理阶乘
      if (token === "!") {
        if (prevTokenType !== "number") {
          throw new Error(`Invalid expression: "${token}" operator must follow a number`);
        }
        const num = operands.pop()!;
        if (num < 0) {
          throw new Error(`Invalid expression: factorial of negative number "${num}!"`);
        }
        let result = 1;
        for (let i = 2; i <= num; i++) {
          result *= i;
        }
        operands.push(result);
        prevTokenType = "number";
        continue;
      }
      // 处理负号
      else if (token === "-") {
        // 负号前面不是数字，也不是运算符，视为 0 参与运算
        if (prevTokenType === "none" || prevTokenType === "parenOpen") {
          operands.push(0);
        }
        // 负号前面是运算符，视为负号
        else if (prevTokenType === "operator") {
          if (sign === -1) {
            throw new Error(
              `Invalid expression: two consecutive operators "${operators[operators.length - 1]}${token}"`,
            );
          }
          sign = -1;
          continue;
        }
      }
      // 之前也是运算符，说明表达式错误
      else if (prevTokenType === "operator") {
        throw new Error(
          `Invalid expression: two consecutive operators "${operators[operators.length - 1]}${token}"`,
        );
      }
      // 处理符号运算
      while (
        operators.length > 0 &&
        precedence[operators[operators.length - 1]] >= precedence[token]
      ) {
        if (operators[operators.length - 1] === "**" && token === "**") {
          // 处理幂运算的右结合性
          break;
        }
        applyTopOperator(operands, operators);
      }
      operators.push(token);
      prevTokenType = "operator";
    }
  }

  // 处理剩余的运算符
  while (operators.length > 0) {
    applyTopOperator(operands, operators);
  }

  return operands.pop()!;
}

function applyTopOperator(operands: number[], operators: string[]): void {
  const op = operators.pop()!;
  const right = operands.pop()!;
  const left = operands.pop()!;
  operands.push(applyOp(op, left, right));
}

function applyOp(op: string, left: number, right: number): number {
  switch (op) {
    case "+":
      return left + right;
    case "-":
      return left - right;
    case "*":
      return left * right;
    case "/":
      return left / right;
    case "**":
      return Math.pow(left, right);
    default:
      throw new Error(`Invalid operator: ${op}`);
  }
}

function testMathEval() {
  const tests = [
    { input: "3 + 5", expected: 8 },
    { input: "10 - 2 * 3", expected: 4 },
    { input: "(1 + 2) * (3 + 4)", expected: 21 },
    { input: "3 + (2 * 4)", expected: 11 },
    { input: "10 / (5 - 3)", expected: 5 },
    { input: "2 + 3 * (4 - 1)", expected: 11 },
    { input: "5 * (6 + 2) - 3", expected: 37 },
    { input: "10 + (2 * (3 + 4))", expected: 24 },
    { input: "((2 + 3) * (4 - 1)) / (5 - 2)", expected: 5 },
    { input: "1 + (2 * (3 + (4 - (5 + (6 - (7 + (8 - (9))))))))", expected: 5 },
    { input: "-1 + (-2) * (-3)", expected: 5 },
    { input: "-(1 + 2)", expected: -3 },
    { input: "-(1 + (-2))", expected: 1 },
    { input: "-(1) + (-2)", expected: -3 },
    { input: "3 + -2", expected: 1 },
    { input: "3 - -2", expected: 5 },
    { input: "3 * -2", expected: -6 },
    { input: "3 / -2", expected: -1.5 },
    { input: "-3 + 2", expected: -1 },
    { input: "-3 - 2", expected: -5 },
    { input: "-3.5 + 2.5", expected: -1 },
    { input: "-3.5 * -2.5", expected: 8.75 },
    { input: "3! ** 3!", expected: 46656 },
  ];
  for (const { input, expected } of tests) {
    const result = mathEval(input);
    if (result !== expected) {
      console.error(`❌ Test failed for input "${input}": expected ${expected}, got ${result}`);
    } else {
      console.log(`✅ Test passed for input "${input}": got ${result}`);
    }
  }
}

testMathEval();