« 回到博客列表

栈计算器

Feb 10th, 2015阅读本文大约需要 5 分钟

简单说两句

用栈实现计算器,这是数据结构中关于栈的一个经典案例,在很多数据结构的教材中也都有明确的算法说明。这里我们给出一个用 JavaScript 实现的版本。

原理

这个案例的原理,是通过建立两个栈,分别存储读入的操作符和数字,在读取过程中判断操作符之间的优先级关系,来进行计算或等待。因此算法的核心其实是要建立起一张关于操作符优先级的关系表,我们可以通过二维数组来记录这张表,并实现比较。

function compare(op1, op2) {
  var table = new Array(7);

  //  1: '>'
  // -1: '<'
  //  0: '='
  //  9: 没有关系
  table[0] = [ 1,  1, -1, -1, -1,  1,  1];
  table[1] = [ 1,  1, -1, -1, -1,  1,  1];
  table[2] = [ 1,  1,  1,  1, -1,  1,  1];
  table[3] = [ 1,  1,  1,  1, -1,  1,  1];
  table[4] = [-1, -1, -1, -1, -1,  0,  9];
  table[5] = [ 1,  1,  1,  1,  9,  1,  1];
  table[6] = [-1, -1, -1, -1, -1,  9,  0];

  // 定位 2 个操作符
  var ops = ['+', '-', '*', '/', '(', ')', '#'];
  var row = ops.indexOf(op1);
  var col = ops.indexOf(op2);

  return table[row][col];
}

table 就是前面说到的优先级关系表,其顺序对应了 ops 中定义的操作符的顺序。其中 # 是我们额外加入的一个标记,用于标记方程式解析的开始和结束,在操作符栈 op 的栈底和方程式的最右边各有一个,其本身并不是操作符。 table[i] 记录了 ops 中第i个操作符在遇到其它操作符时的优先级关系。

有了这张表,接下来我们就可以进行方程式的解析了。首先创建两个栈 numop (在JavaScript中栈其实也是数组),分别用于存储读入的数字和操作符,然后在 op 中线存入一个 # ,用于初始化。

function calculate (formula) {
  var num = []; // 用于存储数字的栈
  var op = []; // 用于存储操作符的栈
  op.push('#'); // 起始符号
  displayStatus(op, num, formula); // 自定义函数,打印初始状态

  var cache = null; // 缓存上一个的符号
  var c = formula.charAt(0); // 获取第一个符号
  while(c != '#' || op[op.length-1] != '#') { // # 表示计算结束
    if( isNumber(c) ) {

      // 处理多位数
      if(cache != null && isNumber(cache)) {
        var tmp = Number(cache)*10 + Number(c);
        num[num.length-1] = tmp;
      } else {
        num.push(c);
      }
      cache = c; // 缓存上一个字符
      formula = formula.substring(1, formula.length);
      c = formula.charAt(0); // 获取下一个符号
    } else { // 非数字,操作符
      switch(compare(op[op.length-1], c)) {
        case -1: // 后者优先级更高,等待
          op.push(c);
          cache = c;
          formula = formula.substring(1, formula.length);
          c = formula.charAt(0);
          break;
        case 0: // 优先级相等,或是 ')'、'#'
          op.pop();
          cache = c;
          formula = formula.substring(1, formula.length);
          c = formula.charAt(0);
          break;
        case 1: // 前者优先级更高,计算
          var o = op.pop();
          var b = num.pop();
          var a = num.pop();
          var r = cal(o, a, b);
          num.push(r);
          cache = c;
          break;
        default:
          break;
      }
    }
    displayStatus(op, num, formula);
  }
  return num[num.length-1];
}

上面代码中的 displayStatus(op, num, formula) 是我自定义的一个函数,用于将解析的过程展现出来,每经过一步之后各个栈里都包含了哪些元素一目了然。 isNumber(c) 用于判断读入的字符是数字还是操作符、 compare(op1, op2) 在第一段代码中已经给出,用于比较两个操作符的优先级、 cal(o, a, b) 用于执行二元运算。这些函数实现起来都很简单,这里就不贴代码了。

程序每次从方程式的左边读入一个字符,判断是数字还是操作符,然后压入对应的栈中,并对 op 栈中最靠近栈顶的两个操作符进行优先级的比较,确定是进行计算还是需要等待更高优先级的计算。如此往复,直到最后 op 只剩下 # ,即为结束。

方程式的读取方式是每次读取一个字符,这就带来一个问题:如果数字>9(即不止个位数,例如:23、768、1024……)怎么办?因此在栈初始化完成之后,我设立了一个变量 cache ,这个变量会缓存上一个读入的字符,和即将读入的字符作比较,如果两者都是数字,就把它们拼接成一个数字。

同理还有一个负数的问题,即减号后面跟一个数字,这时需要对减号进行判断,一方面是判断减号到底是操作符还是数字的一部分,另一方面这种情况通常意味着要么减号前面有一个左括号,要么减号是方程式的第一个字符,即方程式中的第一个数字就是负数。

另外还有一个问题,小数,因为是逐字符读入,因此小数点也会被单独读入,需要手动进行拼接。

好了,现在我们能够正常读取数字,并且正确分辨操作符了,接下来就要根据读入的内容进行解析了:如果读入的是数字,那就直接压入 num 栈中;如果读入的是操作符,那么就要根据操作符之间的优先级关系进行判断,是立即执行计算,还是需要等待观望后序的方程内容。操作符之间的优先级关系无非3种情况:(这里我们约定, op 的栈顶元素为 op1 ,新读取到的操作符为 op2

1. op1 优先级低于 op2

这种情况下,后面有可能还会有优先级更高的运算出现,因此需要先讲当前的状态暂存(即将新读入的操作符压入 op 栈中),并继续读取后序的字符。

2. op1 优先级高于 op2

当出现这种情况时,说明短时间内不会出现比当前栈中已保存的运算优先级更高的运算了,因此可以立即进行一次运算。先不把新读入的字符压栈,从 num 栈的栈顶出栈两个数字,并让 op 栈的栈顶出栈,将这三个元素组合起来进行一次运算,运算结果压回 num 栈中。

3. op1op2 优先级相同

出现这种情况只有两种可能,要么 op 的栈顶是左括号,新读入的是右括号,两者匹配,可以消除;要么 op 栈顶是 # ,新读入的也是 # ,表示方程式读取完毕,计算全部结束。

小结

栈是数据结构中最基本的一种,用栈实现方程式的整式计算更是一个经典的案例,不过大部分的教材都是以10以内正整数的四则运算为例简单描述了一下算法,并未涉及一些特殊的情况,例如负数、小数、多位数等等,因此还是很有必要亲自写一遍感受一下。