后缀表达式与基于栈VM

Manan
Page content

后缀表达式

算术运算表达式有三种形式，分别为“中缀表达式”，“后缀表达式”和“前缀表达式”。

中缀表达式是让数据结合在算符的两侧，例如a * (b + c) - d。这种表达式也是我们使用最多，最符合人类思考方式的算术运算表达形式。

前缀表达式与后缀表达式类似，后缀表达式是将算符置于数据之后，例如a b c + * d -。前缀表达式是将运算符置于数据之前，例如+ * a b c - d。

最常使用的中缀表达式可以通过一定的算法转换为后缀或者前缀表达式。

通过观察不难发现，后缀表达式在计算时是有序的，所谓有序就是我们只需遍历整个表达式就能得到表达式的结果，无需考虑运算符之间的优先级顺序（中缀表达式显然需要考虑算符之间的优先级顺序，而后缀表达式是已经按照运算符顺序进行排好序的表达式序列）。

后缀表达式的计算

  • 算法准备

  1. 后缀表达式

  2. 数据栈

  • 算法阐述

  1. 遍历后缀表达式字符串

  2. 如果字符串是数字，转换为数字并压入数据栈

  3. 如果是支持的算符，根据算符的数据结合性（一元算符结合一个数据，二元算符结合两个数据，不考虑算符的左结合和右结合）从栈中弹出指定数量的数据

  4. 将弹出的数据按照算符计算规则进行计算，并重新压入栈

  • Java代码实现
ArrayDeque<Double> operatorNumberStack = new ArrayDeque<>();
for (String token : tokenStream) {
    if (isSupportedOperator(token.charAt(0))) {
        double a, b = 0.0D;
        switch (token) {
            case "+":
                a = operatorNumberStack.pop();
                b = operatorNumberStack.pop();
                operatorNumberStack.push(b + a);
                break;
            case "-":
                a = operatorNumberStack.pop();
                b = operatorNumberStack.pop();
                operatorNumberStack.push(b - a);
                break;
            case "*":
                a = operatorNumberStack.pop();
                b = operatorNumberStack.pop();
                operatorNumberStack.push(b * a);
                break;
            case "/":
                a = operatorNumberStack.pop();
                b = operatorNumberStack.pop();
                operatorNumberStack.push(b / a);
                break;
            default:
                break;
        }
    } else {
        operatorNumberStack.push(Double.valueOf(token));
    }
}
return operatorNumberStack.pop();

后缀表达式在JVM Bytecode中的体现

在JVM抽象层面，JVM运行是与寄存器无关，因为JVM被设计为一种基于栈的虚拟机。

JVM所有的数据运算都在栈中进行，在一个JVM Stack Frame中有操作数栈（存放数据的栈），本地变量表（存放参数，局部变量和临时变量）两种存放数据的结构。

例如下面一段Java代码和编译为Bytecode之后的指令序列。

Java Code

int a = 1;
int b = 2;
int c = 3;
int d = 4;
int e = a * (b + c) -d;
System.out.println(e);

ByteCode

iconst_1 # 将整数1压入操作数栈
istore_1 # 弹出栈顶数据并放入本地变量表索引为1的位置（变量a）
iconst_2 # 将整数2压入操作数栈
istore_2 # 弹出栈顶数据并放入本地变量表索引为2的位置（变量b）
iconst_3 # 将整数3压入操作数栈 
istore_3 # 弹出栈顶数据并放入本地变量表索引为3的位置（变量c）
iconst_4 # 将整数4压入操作数栈
istore 4 # 弹出栈顶数据并放入本地变量表索引为3的位置（变量d）
iload_1  # 从本地变量表加载索引为1的数据至操作数栈 （变量a）
iload_2  # 从本地变量表加载索引为1的数据至操作数栈 （变量b）
iload_3  # 从本地变量表加载索引为1的数据至操作数栈 （变量c）
iadd     # 从操作数栈弹出两个整数，相加，结果入栈
imul     # 从操作数栈弹出两个整数，相乘，结果入栈
iload 4  # 从本地变量表加载索引为1的数据至操作数栈 （变量d）
isub     # 从操作数栈弹出两个整数，相减，结果入栈
istore 5 # 从栈中弹出一个整数，存入本地变量表索引为5的位置

从编译生成的字节码来看，上述Java代码的运算在字节码层面完全是按照后缀表达式的形式去计算，即a b c + * d -。

这正是得益于后缀表达式的有序性与指令执行的有序性是完美契合的（代码执行通过PC程序计数器将排布在内存中的指令按照顺序执行）所以基于栈的虚拟机设计中在设计数据运算时也会参照这种形式进行。

附录A：中缀表达式转后缀表达式（Java）

public static String me2pe(String expr) {
    expr = expr + ')';
    final ArrayDeque<Character> stack = new ArrayDeque<>();
    stack.push('(');
    final StringBuilder buffer = new StringBuilder();
    for (int i = 0, len = expr.length(); i < len;) {
        final char token = expr.charAt(i);
        if (Character.isDigit(token)) {
            NextIndexAndResult r = nextRealNumberString(expr, i);
            i = r.nextIndex;
            buffer.append(r.result);
            buffer.append(' ');
        } else if (isSupportedOperator(token)) {
            // check operator priority
            if (operatorPriorityTable.get(token) > operatorPriorityTable.get(stack.peek())) {
                stack.push(token);
                i ++;
            } else {
                if (token == ')') {
                    // pop until '('
                    for (;;) {
                        char t = stack.pop();
                        if (t == '(') break;
                        buffer.append(t);
                        buffer.append(' ');
                    }
                    i++;
                } else if (token == '(') {
                    stack.push(token);
                    i++;
                } else {
                    buffer.append(stack.pop());
                    buffer.append(' ');
                }
            }
        } else {
            // other tokens
            i++;
        }
    }
    return buffer.toString();
}

获取完整代码请访问Github仓库：https://github.com/mananBC1st/JavaLeetcode