【JS算法练习】彻底搞懂逆波兰表达式的求法,再复杂的表达式也不用慌~

前言

表达式求值是校招面试/笔试中常考的一道算法题，即可以考察求职者的算法功底，又可以考察求值者思考问题的全面性。下面我们就来看看如何使用逆波兰表达式来求解各类复杂的表达式吧~

问题描述：

以字符串的形式给出表达式，请输出该表达式的求值结果。例如：
输入：‘1+(12*3-4/2)-1’
输出：34

什么是逆波兰表达式？

逆波兰表达式又称为后缀表达式，代表的含义是 *** 作数在前，运算符在后。
比如：1+2，用逆波兰表达式来写的话，就是12+.
而1+2这种写法称为中缀表达式，即运算符在两个 *** 作数之间，也是我们平常最常采用的写法。

逆波兰表达式的优点

逆波兰表达式的优点是可以把复杂表达式转换为可以依靠简单的 *** 作得到计算结果的表达式。
只用两种简单 *** 作：入栈和出栈，就可以搞定任何普通表达式的运算。

逆波兰表达式求值步骤

1. 将表达式字符串转换为表达式数组arr，数组的每个元素为 *** 作数或者运算符（转换为数组的目的是防止有两位及以上的数字时在后缀表达式中无法分辨）
2. 生成逆波兰表达式
   声明两个数组，用于生成逆波兰表达式。opeStack为运算符数组，suffixExp为原表达式数组对应的逆波兰表达式数组（JS中数组既可以用作栈，也可以用作队列）

• 遍历表达式数组arr，遇到数字，则直接压入suffixExp数组中
• 遍历表达式数组arr，遇到运算符，就压入opeStack中。但是运算符在压入opeStack前，需要先判断运算符栈的结构：
  • 如果运算符为空，则直接压入栈.
  • 如果运算符不为空，则需要进一步判断来决定如何处理：
    • 如果当前要入栈的运算符为’+‘或者’-’
      • 如果栈中有元素&无左括号’('，则先d出栈中元素，然后将当前运算符压入栈。
      • 如果栈中有元素&有左括号’(‘，则d出栈中元素直至栈顶元素为左括号’(’
    • 如果当前要入栈的运算符为’*‘或者’/’
      • 如果栈顶元素为’*‘或者’/',则先d出栈顶元素，再入栈当前运算符
      • 如果栈顶元素为’+‘或者’-'‘或者(’，则直接入栈
    • 如果当前要入栈的运算符为左括号’(’
      直接入栈
    • 如果当前要入栈的运算符为右括号’)’
      d出栈中元素，直至’('被d出
• 直至遍历完表达式数组，判断运算符栈是否为空，如果不为空，则依次d栈运算符数组，并压入逆波兰表达式数组中

3. 求解逆波兰表达式
   按照后缀表达式的求解方法，依次遍历逆波兰表达式数组，遇到运算符，就与运算符前的两个数组元素做运算，并将这三个元素替换为求解的结果，直至逆波兰表达式数组剩余一个元素，就是最后我们要求解的结果啦~

算法流程图如下图所示：

代码实现

第一步：把字符串表达式转换为数组表达式

let opeStack = [];
let suffixExp = [];
let numReg = /^[0-9]+$/;

// 把表达式的字符串转换为数组
function str2arr(str) {
    let arr = [];
    let frontNum = 0;
    for (let i = 0; i < str.length; i++) {
        if (numReg.test(str[i])) {
            frontNum = frontNum * 10 + parseInt(str[i]);
            if (i === str.length - 1) {
                arr.push(frontNum);
            }
            continue;
        }
        if (['('].indexOf(str[i]) > -1) {
            arr.push(str[i]);
            continue;
        }
        // 处理当前符号以及当前符号之前的元素
        if (str[i - 1] !== ')') {
            arr.push(frontNum);
        }
        arr.push(str[i]);
        frontNum = 0;
    }
    return arr;
}

第二步：生成逆波兰表达式

// 这里传入的strArr必须是一个数组，不然没法处理大于等于10的数
function createSuffixExp(str) {
    for (let i of str) {
        if (numReg.test(i)) {
            suffixExp.push(i);
        } else if (['*', '/'].indexOf(i) >= 0) {
            if (['*', '/'].indexOf(opeStack[opeStack.length - 1]) > -1) {// 如果运算符里有优先级相同的，就先d栈，再压栈
                suffixExp.push(opeStack.pop());
                opeStack.push(i);
                continue;
            }
            opeStack.push(i);
        } else if ([')'].indexOf(i) >= 0) {
            // d栈，直到d出来的是左括号为止
            let ele = opeStack.pop();
            while (ele !== '(') {
                suffixExp.push(ele);
                ele = opeStack.pop();
            }
        } else if (i === '(') {
            opeStack.push(i);
        } else if (opeStack.length > 0) {
            // 如果没有括号隔着，不会有*在+的下面
            while (opeStack.length > 0 && opeStack[opeStack.length - 1] !== '(') {
                suffixExp.push(opeStack.pop());
            }
            opeStack.push(i);
        } else {
            opeStack.push(i);
        }
    }
    while (opeStack.length > 0) {
        suffixExp.push(opeStack.pop());
    }
}

第三步：计算逆波兰表达式

function calcExp(str) {
    while (str.length > 1) {
        for (let i = 0; i < str.length; i++) {
            if (['+', '-', '*', '/'].indexOf(str[i]) > -1) {
                let num1 = parseInt(str[i - 2]);
                let num2 = parseInt(str[i - 1]);
                let ret = 0;
                switch (str[i]) {
                    case '+':
                        ret = num1 + num2;
                        break;
                    case '-':
                        ret = num1 - num2;
                        break;
                    case '*':
                        ret = num1 * num2;
                        break;
                    case '/':
                        ret = num1 / num2;
                        break;
                }
                str.splice(i - 2, 3, ret);
                break;
            }
        }
    }
    // 使用pop是为了置空str，从而让js的垃圾回收机制收回内存。
    return str.pop();
}

最后我们可以验证一下输出：

let str = '1+(12*3-1)';
// let str = '1+(12*3-4/2)-1';
str = str2arr(str);
// 先把中缀表达式转换为后缀表达式
createSuffixExp(str);
// 接下来是对逆波兰表达式做运算了
console.log(calcExp(suffixExp));

完整代码如下所示：

let opeStack = [];
let suffixExp = [];
let numReg = /^[0-9]+$/;

// 把表达式的字符串转换为数组
function str2arr(str) {
    let arr = [];
    let frontNum = 0;
    for (let i = 0; i < str.length; i++) {
        if (numReg.test(str[i])) {
            frontNum = frontNum * 10 + parseInt(str[i]);
            if (i === str.length - 1) {
                arr.push(frontNum);
            }
            continue;
        }
        if (['('].indexOf(str[i]) > -1) {
            arr.push(str[i]);
            continue;
        }
        // 处理当前符号以及当前符号之前的元素
        if (str[i - 1] !== ')') {
            arr.push(frontNum);
        }
        arr.push(str[i]);
        frontNum = 0;
    }
    return arr;
}

// 这里传入的strArr必须是一个数组，不然没法处理大于等于10的数
function createSuffixExp(str) {
    for (let i of str) {
        if (numReg.test(i)) {
            suffixExp.push(i);
        } else if (['*', '/'].indexOf(i) >= 0) {
            if (['*', '/'].indexOf(opeStack[opeStack.length - 1]) > -1) {// 如果运算符里有优先级相同的，就先d栈，再压栈
                suffixExp.push(opeStack.pop());
                opeStack.push(i);
                continue;
            }
            opeStack.push(i);
        } else if ([')'].indexOf(i) >= 0) {
            // d栈，直到d出来的是左括号为止
            let ele = opeStack.pop();
            while (ele !== '(') {
                suffixExp.push(ele);
                ele = opeStack.pop();
            }
        } else if (i === '(') {
            opeStack.push(i);
        } else if (opeStack.length > 0) {
            // 如果没有括号隔着，不会有*在+的下面
            while (opeStack.length > 0 && opeStack[opeStack.length - 1] !== '(') {
                suffixExp.push(opeStack.pop());
            }
            opeStack.push(i);
        } else {
            opeStack.push(i);
        }
    }
    while (opeStack.length > 0) {
        suffixExp.push(opeStack.pop());
    }
}

// 计算逆波兰表达式
function calcExp(str) {
    while (str.length > 1) {
        for (let i = 0; i < str.length; i++) {
            if (['+', '-', '*', '/'].indexOf(str[i]) > -1) {
                let num1 = parseInt(str[i - 2]);
                let num2 = parseInt(str[i - 1]);
                let ret = 0;
                switch (str[i]) {
                    case '+':
                        ret = num1 + num2;
                        break;
                    case '-':
                        ret = num1 - num2;
                        break;
                    case '*':
                        ret = num1 * num2;
                        break;
                    case '/':
                        ret = num1 / num2;
                        break;
                }
                str.splice(i - 2, 3, ret);
                break;
            }
        }
    }
    // 使用pop是为了置空str，从而让js的垃圾回收机制收回内存。
    return str.pop();
}

let str = '1+(12*3-1)';
// let str = '1+(12*3-4/2)-1';
str = str2arr(str);
// 先把中缀表达式转换为后缀表达式
createSuffixExp(str);
// 接下来是对逆波兰表达式做运算了
console.log(calcExp(suffixExp));