简单的表达式求值
作者/ZF.Yi
一直很想做个比 Windows 自带的高级一点的计算器,能将整个表达式输入,然后求值。这个程序要求读者具备编译原理的一些知识。举个实例来说明程序处理过程。假设要求值的表达式为
:
-25*(56+15)# (其中#号作为表达式结束标志)。
首先对表达式进行词法分析,允许出现的字符为:
{0 ,1, 2 ,3 ,4 ,5 ,6, 7 ,8, 9 . ,+ ,-, *, / ,( ,),#}
分析的结果产生两种类型的单词:操作符和操作数。
操作符包括:
{+, - ,* ,/ ,( ,)}
操作数包括:
int 和 double 类型。
上面表达式产生的单词序列为:
{-25,*,(,56,+,15,)}。
这些单词的类型也需要保存。
词法分析正确后将对产生的单词序列进行语法分析。
定义E为表达式,N为常数(视为终结符)。表达式的产生式可表示如下:
E ' N
E ' (E)
E ' E+E
E ' E-E
E ' E*E
E ' E/E
消除左递归后的产生式(E_为新产生的符号):
E->NE_
E->(E)E_
E_->+EE_
E_->-EE_
E_->*EE_
E_->/EE_
E_->NULL (空串)
可以根据这个产生式构造递归的语法分析器。具体细节就不叙述了,可以阅读源代码。
语法分析正确后就可以求值了,求值时用到一个操作数堆栈和操作符堆栈,以及一个算符优先表(存储了运算符之间的优先关系),具体细节可以阅读源码。