中/后缀表达式

2023-05-11 14:06| 来源: 网络整理| 查看: 265

目录0x01 什么是后缀表达式0x02 后缀表达式的具体应用0x031 JAVA的后缀表达式源码反编译BYTECODEJAVAC的实现二元表达式树节点对象运行时二元表达式树执行过程0x032 C的后缀表达式源码反汇编0x03 简单实现中缀转后缀表达式后缀转中缀表达式0x04 总结

纸上得来终觉浅，绝知此事要躬行

0x01 什么是后缀表达式

人类语言数学表达式：(3+4)*2/(1-5)^2

计算机语言数学表达式：3 4 + 2 * 1 5 - / 2 ^

计算机通过栈的数据结构和对应的指令，实现数学表达式的运算

0x02 后缀表达式的具体应用 0x031 JAVA的后缀表达式源码 /** * 中序表达式：(a + b) * c / (d - e) ^ f * 后序表达式：a b + c * d e - / f ^ */ public int postfix(int a, int b, int c, int d, int e, int f){ return (a + b) * c / (d - e) ^ f; } 反编译

BYTECODE

数字含义如下

25是方法开始的行号 1/2/3/4/5/6是变量在参数列表中的索引 3是最大压栈深度 7是本地变量表长度

指令含义如下

字节码助记符指令含义 0x15 iload 将指定的int型本地变量推送至栈顶 0x60 iadd 将栈顶两int型数值相加并将结果压入栈顶 0x68 imul 将栈顶两int型数值相乘并将结果压入栈顶 0x64 isub 将栈顶两int型数值相减并将结果压入栈顶 0x6c idiv 将栈顶两int型数值相除并将结果压入栈顶 0x82 ixor 将栈顶两int型数值作“按位异或”并将结果压入栈顶 0xac ireturn 从当前方法返回int

实际已经转换完成：3 4 + 2 * 1 5 - / 2 ^

JAVAC的实现二元表达式树节点对象来源：com.sun.tools.javac.tree.JCTree.JCBinary public static class JCBinary extends JCExpression implements BinaryTree { // 表示二元运算符 private int opcode; // 二元表达式左边的表达式 public JCExpression lhs; // 二元表达式右边的表达式 public JCExpression rhs; // 操作符的符号 public Symbol operator; }

javac在语义分析阶段就将源码构建为一颗抽象语法树，并完成了对语法树的标注。语法树如下

运行时二元表达式树

iShot_2023-05-11_12

执行过程来源：com.sun.tools.javac.jvm.Gen#visitBinary // 访问二元表达式com.sun.tools.javac.jvm.Gen.visitBinary public void visitBinary(JCBinary tree) { OperatorSymbol operator = (OperatorSymbol)tree.operator; if (operator.opcode == string_add) { // 对字符串的+进行处理 ... } else if (tree.getTag() == JCTree.AND) { // 特殊处理&& ... } else if (tree.getTag() == JCTree.OR) { // 特殊处理|| ... } else { // 处理二元表达式 // 先处理左表达式 Item od = genExpr(tree.lhs, operator.type.getParameterTypes().head); // 指令压栈 od.load(); // 当执行到这一行时，左表达式已经在栈中 result = completeBinop(tree.lhs, tree.rhs, operator); } } 来源：com.sun.tools.javac.jvm.Gen#completeBinop Item completeBinop(JCTree lhs, JCTree rhs, OperatorSymbol operator) { // 运算符指令code int opcode = operator.opcode; ... // 处理右操作数，然后入栈 genExpr(rhs, rtype).load(); ... // 运算符入栈 code.emitop0(opcode); ... } 0x032 C的后缀表达式源码 int postfix(int a, int b, int c, int d, int e, int f) { return (a + b) * c / (d - e) ^ f; } int main() { postfix(1, 2, 3, 4, 5, 6); return 0; } 反汇编 ;int postfix(int a, int b, int c, int d, int e, int f) { ... ; 参数内存分配，栈上下文检查 ; return (a + b) * c / (d - e) ^ f; mov eax,dword ptr [b] ;将b挪到eax寄存器 mov ecx,dword ptr [a] ;将a挪到ecx寄存器 add ecx,eax ;eac+ecx 结果存到ecx中 mov eax,ecx ;将结果挪到eax中 imul eax,dword ptr [c] ;eax乘以c，结果放到eax中 mov ecx,dword ptr [e] ;e挪到ecx中 mov edx,dword ptr [d] ;d挪到edx中 sub edx,ecx ;edx-ecx，结果放到edx中 mov ecx,edx ;结果挪到ecx中 cdq ;除法准备，符号扩展 idiv eax,ecx ;eax除以ecx，结果放到eax中 xor eax,dword ptr [f] ;eax与f做异或运算，结果放到eax中 ;} add rsp,28h ;栈顶往下挪0x28个字节 ret ;过程执行完成，返回

由反汇编可见，实际运算过程也是a b + c * d e - / f ^

0x03 简单实现中缀转后缀表达式

从左到右遍历中缀表达式的每一个数字和符号。

若是数字就输出，即成为后缀表达式的一部分。

如果是符号，则判断其与栈顶符号的优先级，是*右括号*或*已有栈顶符号优先级（乘除优于加减）大于等于此符号*则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

package ylcComplieTest; import java.util.Stack; public class infixToPostfix { public static String infixToPostfix(String infix) { StringBuilder postfix = new StringBuilder(); Stack stack = new Stack(); for (int i = 0; i < infix.length(); i++) { char c = infix.charAt(i); // 如果是数字或字母，直接加入后缀表达式 if (Character.isLetterOrDigit(c)) { postfix.append(c); } // 如果是左括号，入栈 else if (c == '(') { stack.push(c); } // 如果是右括号，弹出栈顶元素，直到找到左括号 else if (c == ')') { while (!stack.isEmpty() && stack.peek() != '(') { postfix.append(stack.pop()); } if (!stack.isEmpty() && stack.peek() != '(') { return "Invalid Expression"; } else { stack.pop(); } } // 如果是运算符 else { while (!stack.isEmpty() && precedence(c)

【本文地址】

公司简介

联系我们