algorithmbook 表达式求值

表达式求值

表达式求值是程序设计语言中的一个最基本问题。它的实现是栈应用的又一个典型例子。这里介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。

要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如要对下述表达式求值：

4+（6-10+2*2）*2

首先，要了解算术四则运算的规则。即：

先乘除，后加减；
从左算到右
先括号内，后括号外

由此，这个算术表达式的计算顺序应为：

4+（6-10+2*2）2 = 4+（-4+22）*2 = 4+（-4+4）2 = 4+02 = 4+0 = 4 1

任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成。界限符也就是小括号，运算符包括加减乘除，以及更复杂的求余、三角函数等等。这里我们只讨论比较简单的算术表达式，只包括加减乘除四种运算符。

我们把运算符和界限符统称为算符，根据上述3条运算规则，在运算每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系至多是下面三种关系之一：

θ1 < θ2，θ1的优先权低于θ2
θ1 = θ2，θ1的优先权等于θ2
θ1 > θ2，θ1的优先权大于θ2 下表定义了这种优先关系：

![image_1cjig9ta61iptmic1j4h1qsi18rh1j.png-23.2kB][14]

由规则（3），+、-、*和/为θ1时的优先级均低于“(”但高于右括号”)”，由规则（2），当θ1 = θ2时，令θ1 > θ2。

基于上述的论述，首先，我们来讨论使用算符优先算法来实现表达式的求值。

为实现该算法，我们需要使用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是：

1.首先设置两个栈：操作数栈和操作符栈 2.依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作。

1.若该运算符优先权大于栈顶运算符优先权则该运算符直接进OPTR栈；反之若运算符优先权小于栈顶运算符的优先权，则弹出栈顶运算符，并从操作数OPND栈弹出两个数进行该栈顶运算符的运算，运算结果再加入OPND操作数栈。 2.循环往复地进行第1步判断。直到将该操作符加入OPTR操作符栈

3.表达式读取结束，若两个栈都不为空，则依次弹出OPTR栈中的运算符和OPND栈中的两个操作数，进行运算后，将运算结果在加入OPND栈。直到OPTR栈为空，OPND栈只剩下一个元素，则该元素就是运算结果。

4.中间出现差错，比如最后OPND栈剩下不止一个数，则视为表达式出错。

下面是完整代码：

function evaluate(expression) {
    var OPND_stack = new Stack(); // 操作数栈
    var OPTR_stack = new Stack(); // 操作符栈
    // 遍历这个表达式
    for (var i = 0; i < expression.length; i++) {
        var c = expression.charAt(i);
        // 如果当前字符是数字，也就是操作数
        if (isDigit(c) || c == '.') {
            var stringBulider = ""
            // 操作数的拼接，包括小数点
            while (i < expression.length && (isDigit(c = expression.charAt(i)) || c == '.')) {
                stringBulider += c;
                i++;
            }
            // 操作数入栈
            OPND_stack.push(Number(stringBulider));
            // 跳过本次循环，i的值已经增加过，所以要减去
            i--;
            continue;
        } else {
            // 当前的字符是操作符
            outer: while (!OPTR_stack.isEmpty()) {
                switch (precede(OPTR_stack.top(), c)) {
                    case '<':
                        // 栈顶运算符小于该运算符，该运算符直接入栈
                        OPTR_stack.push(c);
                        break outer;
                    case '=':
                        // 栈顶运算符等于该运算符，只有一种情况，左右括号匹配，弹出左括号
                        OPTR_stack.pop();
                        break outer;
                    case '>':
                        // 栈顶运算符大小该运算符
                        var operator = OPTR_stack.pop();
                        // 如果有多余的操作符却没有操作数可以计算了，那么说明表达式错误
                        try {
                            var opnd2 = OPND_stack.pop();
                            var opnd1 = OPND_stack.pop();
                            OPND_stack.push(operate(opnd1, operator, opnd2));
                        } catch (e) {
                            console.log("表达式有误0！");
                            return
                        }
                        break;
                }
            }
            // 第一次栈为空的情况，直接入栈。还有退栈直至栈为空的情况，当前操作符也需要入栈
            if (OPTR_stack.isEmpty()) {
                OPTR_stack.push(c);
            }
        }
    }
    while (!OPTR_stack.isEmpty()) {
        var optr = OPTR_stack.pop();
        // 如果有多余的操作符却没有操作数可以计算了，那么说明表达式错误
        try {
            var opnd2 = OPND_stack.pop();
            var opnd1 = OPND_stack.pop();
            OPND_stack.push(operate(opnd1, optr, opnd2));
        } catch (e) {
            console.log("表达式有误！");
            return
        }
    }
    if (OPND_stack.size() == 1) {
        return OPND_stack.pop();
    } else {
        console.log("表达式有误！");
        return
    }
    return 0;
}

function isDigit(c) {
    return /[0-9]/.test(c)
}

function operate(opnd1, optr, opnd2) { //运算
    switch (optr) {
        case '+':
            return opnd1 + opnd2;
        case '-':
            return opnd1 - opnd2;
        case '*':
            return opnd1 * opnd2;
        case '/':
            return opnd1 / opnd2;
    }
    return 0;
}
// 比较两个运算符的优先权大小
function precede(θ1, θ2) {
    if (θ1 == '+' || θ1 == '-') {
        if (θ2 == '+' || θ2 == '-' || θ2 == ')') {
            return '>';
        } else {
            return '<';
        }
    } else if (θ1 == '*' || θ1 == '/') {
        if (θ2 == '(') {
            return '<';
        } else {
            return '>';
        }
    } else if (θ1 == '(') {
        if (θ2 == ')') {
            return '=';
        } else {
            return '<';
        }
    } else if (θ1 == ')') {
        return '>';
    }
    return '>';
}
console.log(evaluate("12*(3+4)-6+8/1"))