posts - 20,&
comments - 35,&
trackbacks - 0
◆3.21③& 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。
实现下列函数：char *RPExpression(char *e);/* 返回表达式e的逆波兰式 */
Stack是一个已实现的栈。可使用的相关类型和函数：typedef char SElemT // 栈Stack的元素类型Status InitStack(Stack &s);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SElemType &e);Status StackEmpty(Stack s);SElemType Top(Stack s);
-------------------------------------------------------------------------------------------------
　　拿到题目，要做的第一件事情，就是搞懂题目究竟要我们做什么，很显然，题目中的关键字是&逆波兰式&，那么首先我们要搞懂这个概念。
　　所谓的逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。（摘自维基）
　　举个简单的例子，平常我们写的数学表达式a+b，就是一种中缀表达式，写成后缀表达式就是ab+。再举一个复杂的例子，中缀表达式(a+b)*c-(a+b)/e的逆波兰式是ab+c*ab+e/-。
　　在弄清楚概念以及题目的要求之后，接下来就要编写算法了。那么将一个表达式转换为逆波兰式的算法思想是什么呢？
　　(1)首先，需要分配2个栈，栈s1用于临时存储运算符（含一个结束符号），此运算符在栈内遵循越往栈顶优先级越高的原则；栈s2用于输入逆波兰式，为方便起见，栈s1需先放入一个优先级最低的运算符，在这里假定为'#'；
　　(2)从中缀式的左端开始逐个读取字符x，逐序进行如下步骤：
　　　　　　1.若x是操作数，则分析出完整的运算数（在这里为方便，用字母代替数字），将x直接压入栈s2；
　　　　　　2.若x是运算符，则分情况讨论：
　　　　　　　　　　若x是'('，则直接压入栈s1；
　　　　　　　　　　若x是')'，则将距离栈s1栈顶的最近的'('之间的运算符，逐个出栈，依次压入栈s2，此时抛弃'('；
　　　　　　　　　　若x是除'('和')'外的运算符，则再分如下情况讨论：
　　　　　　　　　　　　　　若当前栈s1的栈顶元素为'('，则将x直接压入栈s1；
　　　　　　　　　　　　　　若当前栈s1的栈顶元素不为'('，则将x与栈s1的栈顶元素比较，若x的优先级大于栈s1栈顶运算符优先级，则将x直接压入栈s1。否者，将栈s1的栈顶运算符弹出，压入栈s2中，直到栈s1的栈顶运算符优先级别低于（不包括等于）x的优先级，或栈s2的栈顶运算符为'('，此时再则将x压入栈s1;
　　(3)在进行完(2)后，检查栈s1是否为空，若不为空，则将栈中元素依次弹出并压入栈s2中（不包括'#'）；　　　　　　&
　　(4)完成上述步骤后，栈s2便为逆波兰式输出结果。但是栈s2应做一下逆序处理，因为此时表达式的首字符位于栈底；
-------------------------------------------------------------------------------------------------
三、代码（C/C++）&
1 char *RPExpression(char *e)
2 /* 返回表达式e的逆波兰式 */
//栈s1用于存放运算符，栈s2用于存放逆波兰式
Stack s1,s2;
InitStack(s1);
InitStack(s2);
//假设字符'#'是运算级别最低的运算符，并压入栈s1中
Push(s1,'#');
//p指针用于遍历传入的字符串，ch用于临时存放字符,length用于计算字符串长度
char *p=e,
int length=0;
for(;*p!='\0';p++)//逐个字符访问
switch(*p)
//遇'('则直接入栈s1
Push(s1,*p);
//遇')'则将距离栈s1栈顶的最近的'('之间的运算符，逐个出栈，依次送入栈s2,此时抛弃'('
while(Top(s1)!='(')
Pop(s1,ch);
Push(s2,ch);
Pop(s1,ch);
//遇下列运算符，则分情况讨论：
//1.若当前栈s1的栈顶元素是'('，则当前运算符直接压入栈s1；
//2.否则，将当前运算符与栈s1的栈顶元素比较，若优先级较栈顶元素大，则直接压入栈s1中,
否则将s1栈顶元素弹出，并压入栈s2中，直到栈顶运算符的优先级别低于当前运算符，然后再将当前运算符压入栈s1中
for(ch=Top(s1);ch!='#';ch=Top(s1))
if(ch=='(')
Pop(s1,ch);
Push(s2,ch);
Push(s1,*p);
for(ch=Top(s1);ch!='#'&&ch!='+'&&ch!='-';ch=Top(s1))
if(ch=='(')
Pop(s1,ch);
Push(s2,ch);
Push(s1,*p);
//遇操作数则直接压入栈s2中
Push(s2,*p);
//若栈s1非空，则将栈中元素依次弹出并压入栈s2中
while(!StackEmpty(s1)&&Top(s1)!='#')
Pop(s1,ch);
Push(s2,ch);
//最后将栈s2输出，逆序排列成字符串;
result=(char *)malloc(sizeof(char)*(length+1));
*result='\0';
for(;!StackEmpty(s2);result--)
Pop(s2,ch);
-------------------------------------------------------------------------------------------------&
&　　对于实现逆波兰式算法，一开始不懂得概念的时候的确不知道如何入手，在摸清思路后，其实难度并不大，关键在于逻辑要清晰，而且要细心，写这段代码的时候很痛苦，共用了两天的时间（真的好菜）。
　　另摘录维基及度娘中关于实现逆波兰式的意义：（摘自百度）
　　　　为什么要将看似简单的中序表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。　　　　
　　逆波兰式的意义：（摘自维基）
　　　　当有操作符时就计算，因此表达式并不是从右至左整体计算而是每次由中心向外计算一部分，这样在复杂运算中就很少导致操作符错误。
　　　　堆栈自动记录中间结果，这就是为什么逆波兰计算器能容易对任意复杂的表达式求值。与普通科学计算器不同，它对表达式的复杂性没有限制。
　　　　逆波兰表达式中不需要括号，用户只需按照表达式顺序求值，让堆栈自动记录中间结果；同样的，也不需要指定操作符的优先级。
　　　　逆波兰计算器中，没有&等号&键用于开始计算。
　　　　逆波兰计算器需要&确认&键用于区分两个相邻的操作数。
　　　　机器状态永远是一个堆栈状态，堆栈里是需要运算的操作数，栈内不会有操作符。
　　　　教育意义上，逆波兰计算器的使用者必须懂得要计算的表达式的含义。
阅读(...) 评论()中缀表达式，波兰表达式、逆波兰表达式
波兰式、逆波兰式是《数据结构》课程中讲解关于栈的时候提到的，栈是很简单的一种数据结构。但是这些理论的提出却是计算机早期发展领域的重大突破，值得仔细回味。
1. 中缀表达式
我们在数学中学到的表达式被称为中缀表达式，操作符号在操作数中间，比如 2 + 3 * (5 -
1)。对人类而言，这种表达方式显而易见，求值也很直接，先算乘除再算加减，先算括号内再算括号外。
然而，这个表达式对于计算机而言却很费解。你可能会有疑问：这有什么难理解的嘛，在JavaScript、Python或者Ruby，甚至是Java里面都可以通过eval_r("2
+ 3 * (5 -
1)")来计算这个表达式。当然，这里的计算机并不是指现而今强大的计算机和高级编程语言，而是指上个世纪中页还处于发展初期的计算机。
2. 前缀表达式
早在1920年，波兰科学家扬·武卡谢维奇就发明了一种不需要括号的表示法，可以用来表示一个计算表达式。即将操作符号写在操作数之前，也就是前缀表达式，即波兰式（Polish
Notation, PN）。这种表达式直到1960年计算机出现后才发挥出其威力。
比如2 + 3 * (5 - 1)这个表达式的前缀表达式为+ 2 * 3 - 5 1来表示。
阅读这个表达式需要从左至右读入表达式，如果一个操作符后面跟着两个操作数时，则计算，然后将结果作为操作数替换这个操作符和两个操作数，重复此步骤，直至所有操作符处理完毕。从左往右依次读取，直到遇到-
5 1，做计算后，将表达式替换为+ 2 * 3 4，然后从左往右再次读取，直到遇到* 3 4，做计算后将表达式替换为+ 2
12，然后从左往右依次读取，读到+ 2 12，计算得到14，到此结束。
可以看到，这种计算过程也相当复杂，需要多次遍历表达式，而且需要识别一个操作符后面跟着两个操作数这种模式，相比而言，下文中的逆波兰式要更为直接和简单。
如果你熟悉各种编程语言的话，这很像Lisp语言中的表达式（如下代码）。需要注意的是，Lisp语言中的括号并不是数学意义上的的括号，Lisp中的函数是可以携带多个参数的，比如(+
1 2 3)，因此需要使用括号来标明函数参数。
Clojure1.5.1
user=&(+2(*3(-51)))14
3. 后缀表达式
后缀表达式也称为逆波兰式（Reverse Polish Notation,
RPN），更加广为人知一些，和前缀表达式刚好相反，是将操作符号放置于操作数之后，比如2 + 3 * (5 -
1)用逆波兰式来表示则是：2 3 5 1 - * +。
逆波兰式的计算也是从左往右依次读取，当读到操作符时，将之前的两个操作数做计算，然后替换这两个操作数和操作符，接着读取，重复此步骤。对于这个表达式，读到5
1 -，得到4，然后读取乘号，取出前面的3和上一步的计算结果4，并计算，到12，接着读取加号+，计算2 12
+得到14，计算结束。
上面这个步骤可以很容易的用栈来实现：
从左往右依次读取表达式，如果是数字则将该数字压栈，如果是符号，则将之前的两个数字出栈，做计算后，将计算结果压栈，直到表达式读取结束。栈中剩下的一个数就是计算结果。
逆波兰式看起来像波兰式反过来，比如5 + 1的波兰式是+ 5 1，逆波兰式为5 1 +或者1 5
+。也很明显，逆波兰式并不是简单的将波兰式反过来，因为，减法和除法中减数和被减数、除数与被除数是不能交换的，即- 10 5和- 5
10就完全不一样。
4. 中缀表达式到后缀表达式的转换
因为通过后缀表达式来进行计算只需要一个栈即可，从硬件和软件上实现都是极为便利的，因此逆波兰式在计算机领域的应用更加广泛，因此将中缀表达式转换为逆波兰式非常重要。
依然仅仅使用栈就可以将中缀表达式转换成逆波兰式，转换过程如下：
从左往右遍历中缀表达式中的每个数字和符号，弱是数字就输出，成为逆波兰式的一部分；
如果是右括号，或者是其他符号并且比当前栈顶符号的优先级低，则栈顶元素依次出栈并输出；
然后将当前符号进栈，重复以上操作直到结束。
还是以2 + 3 * (5 - 1)为例：
首先读入数字2，直接将其输出，输出为2，栈为空
接着读入加号+，由于栈为空，因此将其进栈，输出为2，栈为+
接着读入数字3，直接将其输出，输出为2 3，栈为+
接着读入乘号*，比栈顶元素优先级高，进栈，输出为2 3，栈为+ *
读入左括号(，直接进栈，输出2 3，栈为+ * (
读入数字5，直接将其输出，输出为2 3 5，栈为+ * (
读入减号-，栈顶元素为左括号，进栈，输出为2 3 5，栈为+ * ( -
读入数字1，直接将其输出，输出为2 3 5 1，栈为+ * ( -
读入右括号，依次输出栈顶元素，直到左括号，括号不输出，输出2 3 5 1 -，栈为+ *
已经无元素可读，依次输出栈顶元素，直到栈为空，输出2 3 5 1 - * +，栈为空
这样可以仅仅使用栈，首先将中缀表达式转换为逆波兰式，然后用本文第3节中的方法对后缀表达式进行求值，整个过程使用栈来完成即可。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。逆波兰式的生成_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
逆波兰式的生成
上传于|0|0|文档简介
&&逆波兰式的生成 报告
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩17页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢算术表达式采用逆波兰式表示时不用括号，可
作者：update来源：网络转载日
●算术表达式采用逆波兰式表示时不用括号，可以利用（
）进行求值。与逆波兰式ab-cd+*对应的中缀表达式是（
）。A．数组&&&& &B．栈&&&& &C．队列&&&& &D．散列表A．a-b+c*d&&&&& B．(a-b)*c+d&&&&& C．(a-b)*(c+d)&&& &D． a-b*c+d试题答案：B,C试题来源：2011年上半年数据库系统工程师考试试题