逆波兰式.doc

一、题目◆③假设表达式由单字母变量和双目四则运算算符构成。试写一个算法,将一个通常书写形式且书写正确的表达式转换为逆波兰式。实现下列函数:char*RPExpression(char*e);/*返回表达式e的逆波兰式*/Stack是一个已实现的栈。可使用的相关类型和函数:typedefcharSElemType;//栈Stack的元素类型StatusInitStack(Stack&s);StatusPush(Stack&s,SElemTypee);StatusPop(Stack&s,SElemType&e);StatusStackEmpty(Stacks);SElemTypeTop(Stacks);-------------------------------------------------------------------------------------------------二、思路拿到题目,要做的第一件事情,就是搞懂题目究竟要我们做什么,很显然,题目中的关键字是“逆波兰式”,那么首先我们要搞懂这个概念。所谓的逆波兰表示法(ReversePolishnotation,RPN,或逆波兰记法),是一种数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。(摘自维基)举个简单的例子,平常我们写的数学表达式a+b,就是一种中缀表达式,写成后缀表达式就是ab+。再举一个复杂的例子,中缀表达式(a+b)*c-(a+b)/e的逆波兰式是ab+c*ab+e/-。在弄清楚概念以及题目的要求之后,接下来就要编写算法了。那么将一个表达式转换为逆波兰式的算法思想是什么呢?(1)首先,需要分配2个栈,栈s1用于临时存储运算符(含一个结束符号),此运算符在栈内遵循越往栈顶优先级越高的原则;栈s2用于输入逆波兰式,为方便起见,栈s1需先放入一个优先级最低的运算符,在这里假定为'#';(2)从中缀式的左端开始逐个读取字符x,逐序进行如下步骤:,则分析出完整的运算数(在这里为方便,用字母代替数字),将x直接压入栈s2;,则分情况讨论:若x是'(',则直接压入栈s1;若x是')',则将距离栈s1栈顶的最近的'('之间的运算符,逐个出栈,依次压入栈s2,此时抛弃'(';若x是除'('和')'外的运算符,则再分如下情况讨论:若当前栈s1的栈顶元素为'(',则将x直接压入栈s1;若当前栈s1的栈顶元素不为'(',则将x与栈s1的栈顶元素比较,若x的优先级大于栈s1栈顶运算符优先级,则将x直接压入栈s1。否者,将栈s1的栈顶运算符弹出,压入栈s2中,直到栈s1的栈