1.前 言
在计算机中,算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同
的优先级,又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行。因而在程序
设计时,借助栈实现。
算法输入:一个算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入)。为
简化,规定操作数只能为正整数,操作符为+、-*、/,用#表示结束。
算法输出:表达式运算结果。
算法要点:设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的
同时,完成运算符和运算数的识别处理,以及相应运算。
2.概要设计
2.1 数据结构设计
任何一个表达式都是由操作符,运算符和界限符组成的。我们分别用顺序栈来寄存表达
式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储
结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针 top 指示
栈顶元素在顺序栈中的位置,base 为栈底指针,在顺序栈中,它始终指向栈底,即 top=base
可作为栈空的标记,每当插入新的栈顶元素时,指针 top 增 1,删除栈顶元素时,指针 top
减 1。
2.2 算法设计
为了实现算符优先算法。可以使用两个工作栈。一个称为 OPTR,用以寄存运算符,另
一个称做 OPND,用以寄存操作数或运算结果。
1.首先置操作数栈为空栈,表达式起始符”#”为运算符栈的栈底元素;
2.依次读入表达式,若是操作符即进 OPND 栈,若是运算符则和 OPTR 栈的栈顶运算符比
较优先权后作相应的操作,直至整个表达式求值完毕(即 OPTR 栈的栈顶元素和当前读入的
评论1