面试题：Go token语法规则下的表达式解析

Question

假设给定一个符合Go语法规则的简单算术表达式字符串（例如 "3 + 5 * 2"），基于Go token的语法规则，如何将其解析为一个可以计算结果的表达式结构？请描述大致的解析步骤和涉及到的token相关操作。

Answer 1

1. 词法分析（Lexical Analysis）：
   • 使用Go的token包和相关的词法分析工具（如text/scanner包）将输入的字符串分解为一个个的token。例如，对于表达式 "3 + 5 * 2"，会生成类似token.INT（值为3），token.PLUS，token.INT（值为5），token.ASTERISK，token.INT（值为2）等token。
2. 语法分析（Syntax Analysis）：
   • 采用递归下降分析法或其他语法分析算法。
   • 从词法分析得到的token序列构建语法树。例如，对于上述表达式，可能构建出一棵简单的二叉树，根节点为token.PLUS，左子树节点为token.INT（值为3），右子树根节点为token.ASTERISK，token.ASTERISK的左子树节点为token.INT（值为5），右子树节点为token.INT（值为2）。
   • 在语法分析过程中，需要处理运算符的优先级。例如，乘法*的优先级高于加法+，所以在构建语法树时，乘法部分会先被组合成一个子树。
3. 计算表达式结果：
   • 对构建好的语法树进行遍历（如后序遍历）。
   • 在后序遍历过程中，当遇到操作数（如token.INT类型的token）时，将其值压入栈中。
   • 当遇到运算符（如token.PLUS、token.ASTERISK等）时，从栈中弹出相应数量的操作数（对于二元运算符是两个操作数），进行运算，并将结果压回栈中。
   • 遍历结束后，栈顶元素即为表达式的计算结果。