JavaScript 算术表达式求解算法 - 使用栈实现运算优先级

JavaScript 算术表达式求解算法 - 使用栈实现运算优先级

本算法使用 JavaScript 栈数据结构来实现算术表达式的求解，通过比较运算符优先级，正确计算结果。

示例代码：

var arr = [2, '+', 3, '+', 4, '-', 5, '*', 6, '/', 2, '+', 8, '='];

var oShi = document.getElementById('shi');
var oAns = document.getElementById('ans');
oShi.innerText = arr.join('');

var aShu = [];
var aFu = [];
var type, val;

for (var i = 0; i < 3; i++) {
  type = typeof arr[i];
  if (type == 'number')
    aShu.push(arr[i]);
  else
    aFu.push(arr[i]);
}

for (var i = 3; i < arr.length; i++) {
  type = typeof arr[i];
  if (type == 'number') {
    aShu.push(arr[i]);
  } else {
    var w = arr[i];
    var D = aFu.pop();
    judge(w, D);
  }
}

function judge(w, D) {
  switch (w) {
    case '*':
    case '/':
      if (D == '+' || D == '-') {
        aFu.push(D);
        aFu.push(w);
      } else {
        var num2 = aShu.pop();
        var num1 = aShu.pop();
        switch (D) {
          case '+':
n            val = num1 + num2;
            aShu.push(val);
            if (aFu.length == 0) {
              D = aFu.pop();
              judge(w, D);
            } else {
              aFu.push(w);
            }
        }
      }
      break;
    default:
      var num2 = aShu.pop();
      var num1 = aShu.pop();
      switch (D) {
        case '+':
n          val = num1 + num2;
          aShu.push(val);
          if (aFu.length == 0) {
            D = aFu.pop();
            judge(w, D);
          } else {
            aFu.push(w);
          }
      }
  }
}

oAns.innerText = aShu[0];

算法解释：

1. 栈初始化： 将算式的前三个元素（数字或运算符）分别入栈 aShu 和 aFu。
2. 循环遍历： 从第四个元素开始循环，判断元素类型：
   • 数字： 将数字入栈 aShu。
   • 运算符： 将当前运算符 w 与栈顶运算符 D 进行比较，根据运算符优先级进行处理：
     • 栈外运算符优先级高于栈内运算符： 执行栈顶运算，并将结果入栈 aShu，并将当前运算符入栈 aFu。
     • 栈内运算符优先级高于栈外运算符： 直接将当前运算符入栈 aFu。
3. 递归处理： 当栈顶运算符 D 的优先级高于当前运算符 w 时，递归调用 judge 函数进行处理，直到栈顶运算符 D 的优先级不再高于当前运算符 w 为止。
4. 最终结果： 遍历完所有元素后，栈 aShu 中的第一个元素即为计算结果。

注意：

• 此算法仅支持加减乘除四则运算。
• 此算法假设输入的算式语法正确，没有括号等特殊符号。

应用场景：

• 在线计算器
• 代码解释器
• 数据处理工具等

优化方向：

• 添加括号支持
• 增加其他运算符支持
• 提高代码可读性和可维护性