表达式求值及符号推导

英昌盛

(吉林师范大学 计算机学院，吉林 四平 136000)

0 引言

表达式的分析、求值等运算是编译程序中的一个关键部分。研究翻译程序的工作原理和工作流程，对于教师的教学和研究，对于学生理论联系实际都具有较为实用的意义和价值。

1 系统设计及概要设计

1.1 运算符和数据类型的支持

系统支持算术运算、关系运算和逻辑运算。算术运算符有包括:()、+、-、*、/、^(乘方)，其中^为新增运算符。逻辑运算符包括:!、＆(逻辑与为化简运算符)、|(逻辑或为化简运算符)。关系运算符包括:＞、＞=、==、_(负号)。

系统支持整数及浮点数。在进行算术运算、关系运算、逻辑运算时运算规则和结合性基本同C语言中相应的规则一致。

1.2 数据结构

用户输入的数据是随机的，同时程序处理数据时用栈这种结构实现较好，所以系统采用两个链栈［1］来保存运算量和运算符。因输入的变量个数无法确定，系统采用动态生成链表［2］来存储。

2 系统实现

2.1 算符优先级及数据结构

系统使用结构体数组charindex［］和OPTable［］保存运算符及其对应的优先级。charindex［］用来存放运算符和该运算符的栈外、内优先级在OPTable［］中的下标。charindex［］结构体数组的op域用来保存第i个运算符，index域用来存放第i个运算符在OPTable［］结构体数组相应元素中的下标，如表1［3］所示。

表1 运算符及其栈内、外优先级

OPTable［］的opri域和ipri域分别表示charindex［］数组中第i个运算符对应的栈外、栈内优先级。为方便运算和节省栈的域，OPTable［］的元素个数较charindex［］的元素个数多三项。系统只用一个整数表示一个运算符，而＞=，==，＜=等运算符都是两个字符组成的字符串，不便于统一处理，经研究发现完全可以用＜、=、＞三个运算符的在OPTable［］中的下标值分别加1来表示＜=、==、＞=在OPTable［］中的下标值，因而＜、=、＞三者之间的索引值按2递增。具体定义如下:

2.2 处理规则

(1)初始化时在运算栈内压入一个#;同时#作为表达式结束标记。

(2)若栈外运算符的栈外优先级比栈顶运算符的栈内优先级高，则栈外运算符入栈;否则栈顶运算符退栈，并取出相应个数的运算量进行运算，把运算结果压回运算量栈，直到栈外运算符的栈外优先级比栈顶运算符的栈内优先级高为止，将栈外运算符入栈;若栈外运算符的栈外优先级和栈顶运算符的栈内优先级相等，则栈顶运算符一定为’(’，此时为()的情况，作出错处理。

(3)运算符退栈时，若遇到栈外运算符的栈外优先级和栈顶运算符的栈内优先级相等情况(此时一定是括号)，则弹出栈顶运算符，抛弃栈外运算符。

(4)若运算完毕运算量栈只剩一个运算量、符号栈空，则运算结果正确，其他情况则为错误。

(5)若 a＞0，则 -a=a*(-1)。

(6)程序中不支持在表达式中有赋值运算。即若遇到‘=’而其后的第一个字符不是‘=’则认为出错。

2.3 核心实现

函数evaluate用于求解经过规范化的用户输入表达式，有四个参数:s为经过规范化后的用户输入表达式;s1为运算量栈指针;s2为运算符栈指针;s3为变量链表指针。程序中首先定义了一些临时变量，然后在运算符栈内压入#的索引及其栈外、栈内优先级作为标记如下:

s2=pushstack(s2，0，1，1);/*#的索引、栈内外级入栈*/

在表达式未结束且已扫描过的部分表达式合法的情况下循环处理。若是数字或小数点则进入数值处理分支并继续读取，并将运算量压入运算量栈中。若读到的是字母，则进入变量分支，并在变量表中进行查找变量值并压入运算量栈之中。

对于运算符首先查找运算符表，然后在OPTable［］表中找到其对应的栈内、外优先级，并对栈外运算符的栈外优先级和栈顶运算符的栈内优先级作相应的比较，根据比较结果进行相应的运算。

［1］严蔚敏.数据结构［M］.北京:清华大学出版社出版，2009.

［2］谭浩强.C语言程序设计教程［M］.4版.北京:清华大学出版社出版，2010.

［3］唐策善.数据结构—用C语言描述.［M］.北京:高等教育出版社，2003.