逆波兰表示法简介

逆波兰表示法俗称后缀表达式，是算术表达式的一种形式。

举个例子，我们常见的算术表达式3*4+5+6叫做中缀表达式，如果将其写成后缀表达试，就会变成34*5+6+，显然这样的运算符跑到操作数后面去了。

和中缀表达式想比，后缀表达式显得让人难以理解，但是对计算机而言却是非常友好的，因为它的计算模式和栈的数据结构非常吻合。例如，如果我们在计算器中输入一段表达式例如3*4+5+6，计算器就会把表达式转换成34*5+6+，然后再进行计算得出我们的值。

计算原理

逆波兰表达式的计算原理就是：把表达式拆成数组结构，从左到右进行扫描，遇到运算符就对其前面的操作数进行运算，直到没有任何操作符为止。

下面演示计算过程：

[3, 4, *, 5, +, 6, +]
[12, 5, +, 6, +]
[12, 5, +, 6, +]
[17, 6, +]
[23]

最后的结果就是数组的第一个字段：23。

我们先不忙着用代码实现上面的扫描计算，因为后缀表达式写起来太不习惯了，所以先得把一个中缀表达式转换成后缀表达式。

实现转换

常用的转换算法为调度场算法，这里就不详细介绍算法的原理了，下面的代码也是基于此算法。

首先，我们定义了一系列操作符，并提供一些通用的方法。

// RNP.js

const operatorLevel = {
  '#': -1,
  '+': 0,
  '-': 0,
  '*': 1,
  '/': 1,
  'f': 2, // 取负值
  '(': 10,
  ')': 10,
}

const isNumber = (char) => {
  return /[0-9.]/.test(char);
}

const isOperator = (char) => {
  return /[+\-/*()]/.test(char);
}

const isValid = (char) => {
  return isNumber(char) || isOperator(char);
}

在具体算法开始前定义2个栈，分别是 operatorStack - 临时运算符栈，rnpStack - 逆波兰表达式栈

function rnp(expression){
    // 临时运算符栈
    const operatorStack = ['#'];
    // 逆波兰式栈
    const rnpStack = [];

    const l = expression.length;
    let index = 0;
    // 临时操作数
    let tempNumber = '';
    // ...
}

然后从左到右一次遍历表达式字符串。

如果是操作数，直接入栈rnpStack，如果是运算符就有几种情况需要处理。

如果不是括号，则检查运算符优先级大于栈顶优先级，直接入栈。否则将栈顶元素依次出栈放入rnpStack，直到优先级低于当前操作数为止。这里需要注意的是，如果是-可能是取负值，所以要额外判断和处理。

let l2 = operatorStack.length;
while (l2) {
  l2--;
  const topOperator = operatorStack[l2];

  // 判断取负值
  if (char === '-') {
    const preChar = expression[index - 1];
    // 如果是对当前值取负
    if (index === 0 || (preChar !== ')' && isOperator(preChar))) {
      operatorStack.push('f');
      break;
    }
  }

  // 括号运算符直接插入
  if (topOperator === '(' || topOperator === ')') {
    operatorStack.push(char);
    break;
  }

  // 判断优先级
  if (operatorLevel[char] < operatorLevel[topOperator]) {
    operatorStack.pop();
    rnpStack.push(topOperator);
  } else {
    operatorStack.push(char);
    break;
  }
}

如果是左括号，也直接入栈rnpStack。

如果是右括号，需要从operatorStack中依次出栈，找到最近的(为止，然后将(以外的其他预算符全部入栈rnpStack。

const temp = [];
let matched = false;

while (operatorStack.length) {
  const operator = operatorStack.pop();
  if (operator === '(') {
    rnpStack.push(...temp);
    matched = true;
    break;
  }
  temp.push(operator);
}

// 这里对括号的匹配情况做检查
if (!matched) {
  throw new Error(`位置${index}存在多余的')'`);
}

遍历完成后，将operatorStack中剩余的预算符依次入栈到rnpStack。

// 将剩余的操作符入栈
let op;
while (op = operatorStack.pop()) {
if (op === '(') {
  throw new Error(`存在未关闭的(`)
}

if (op !== '#') {
  rnpStack.push(op);
}

最后得到的rnpStack就是逆波兰表达式数组。

计算

现在用上面得到的rnpStack来完成扫描计算算法。

原理就是定义一个栈，如果遇到操作数就入栈，如果遇到操作符就根据类型选择数据出栈，并将计算的结果入栈。

function calRNP(rnpArr) {
  const operandStack = [];
  let l = rnpArr.length;

  let index = 0;
  while (index < l) {
    const item = rnpArr[index];

    switch (item) {
      case 'f': {
        const op = operandStack.pop();
        operandStack.push(-op);
        break;
      }
      case '+': {
        const op1 = operandStack.pop();
        const op2 = operandStack.pop();
        operandStack.push(op1 + op2);
        break;
      }
      case '-': {
        const op1 = operandStack.pop();
        const op2 = operandStack.pop();
        operandStack.push(op1 - op2);
        break;
      }
      case '*': {
        const op1 = operandStack.pop();
        const op2 = operandStack.pop();
        operandStack.push(op1 * op2);
        break;
      }
      case '/': {
        const op1 = operandStack.pop();
        const op2 = operandStack.pop();
        operandStack.push(op1 / op2);
        break;
      }
      default:
        operandStack.push(item);
    }

    index++;
  }

  if (isNaN(operandStack[0]) || operandStack.length > 1) {
    throw new Error('不合法的算术表达式');
  }

  return operandStack[0];

}

最后得到的数组，如果长度为1，则第一个元素就是计算的最终值。

最后，让我们试一下吧。

1
2
3

const rnpArr = RNP('3*(32*(2+10)+10)');
console.log(rnpArr); // [ 3, 32, 2, 10, '+', '*', 10, '+', '*' ]
console.log(calRNP(rnpArr)); // 1182

参考资料

百度百科-逆波兰式

wiki-调度场算法

此处有本文的完整代码。