表达式计算

算法的思想：设置两个工作栈：运算符栈OPTR和操作数栈OPND。操作数栈也放表达式的运算结果。首先置操作数栈为空栈，置运算符栈的栈底为表达式的起始符#。依次读入表达式中的每个字符，若是操作数则进OPND栈；若是运算符，则和OPTR中的栈顶元素做比较再操作，直至表达式求置完毕。 这里重点介绍中缀表达式转为后缀表达式，并对后缀表达式求值。

 1）   中缀表达式转为后缀表达式

        设中缀表达式和后缀表达式分别在向量IFX和PFX中，用栈S实现中缀式转为后缀式，对IFX中表达式从左到右扫描，设TOKEN是扫描读到的符号，转换算法可描述如下。

(1)栈初始化。

  (2)从左到右扫描向量IFX，重复下述两步操作，直到表达式尾。

1 从IFX中取出下个TOKEN(数字、运算符、左括号、右括号)；

2  CASE TOKEN OF  

 '('：将TOKEN压入栈S;  

操作数：将操作数直接送入PFX;

操作符：如栈空或TOKEN比栈顶元素优先级高，将TOKEN进栈；

否则，退栈并将退栈元素送入PFX，然后再将TOKEN与新栈顶元素比较之;

‘)’：退栈并将退栈元素送PFX，直到碰到左括号，左括号退栈不送PFX。

 (3)当遇到中缀表达式结束符号，连续退栈并送退栈元素到PFX，直至栈空。

2）   对后缀表达式求值

用实型数栈S存放计算后缀式的中间及最终结果，求值算法可描述如下。

(1)栈初始化。

(2)从左到右扫描向量PFX，重复下述两步操作，直到表达式尾。

1 从PFX中取出下个TOKEN(操作数、运算符)

2 CASE TOKEN OF

操作数：将操作数直接送入栈S1;

操作符：出栈两个操作数，对其进行TOKEN操作，结果压人栈S1

    (3)当遇到后缀表达式结束符号，栈顶的值就是结果(应是栈中唯一元素)。