表达式求值及符号推导

2012-09-21英昌盛

长春大学学报 2012年10期

关键词：运算符运算量数据结构

英昌盛

(吉林师范大学计算机学院，吉林四平 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)程序中不支持在表达式中有赋值运算。即若遇到‘=’而其后的第一个字符不是‘=’则认为出错。