> 博客详情
栈操作是常数时间操作，后缀表达式花费的是O(N).
中缀转后缀表达式算法描述：
（1）遇到操作数，直接输出；
（2）栈为空时，遇到操作符，入栈；
（3）遇到左括号、入栈；
（4）遇到右括号，执行出栈操作，并输出出栈元素，直到遇到左括号，左括号不输出；
（5）遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该操作符的栈顶元素，然后将该操作符入栈；
（6）最终将栈中的元素依次出栈，输出。
经过上面的步骤，得到的输出既是转换得到的后缀表达式。
举例：a+b*c+(d*e+f)*g ---------& abc*+de*f+g*+
public&class&InToPostfix&{
private&Stack&Character&&s;
private&String&
private&String&output="";
public&InToPostfix(String&input)&{
this.input&=&
s&=&new&Stack&Character&();
public&String&doTrans(){
for(int&i=0;&i&input.length();&i++){
char&c&=&input.charAt(i);
switch(c){
//2.栈为空时，遇到操作符，入栈
//3.遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该操作符的栈顶元素，然后将该操作符入栈；
gotOper(c,1);
gotOper(c,2);
//4.遇到（，入栈
s.push(c);
//5.遇到），出栈，只接输出，直到遇到（，不输出
gotParent();
//1遇到操作数，直接输出
output&+=c;
//6.最后将栈中的元素全部输出
while(!s.isEmpty()){
output&+=&s.pop();
private&void&gotOper(char&ch,&int&prior1){
while(!s.isEmpty()){
char&top&=&(char)&s.pop();
if(top=='('){
s.push(top);
int&prior2;
if(top=='+'||top=='-'){
prior2&=&1;
prior2&=&2;
if(prior2&&&prior1){
s.push(top);
output&+=&
s.push(ch);
private&void&gotParent(){
while(!s.isEmpty()){
char&c&=&(char)&s.pop();
if(c&!=&'('){
output&+=&c;
public&static&void&main(String[]&args)&{
String&input&=&"a+b*c+(d*e+f)*g";
InToPostfix&inTo&=&new&InToPostfix(input);
String&output&=inTo.doTrans();
System.out.println(output);
支付宝支付
微信扫码支付
打赏金额: ￥
已支付成功
打赏金额: ￥继续查找其他问题的答案？
其他答案(0)
找答案神器
上学吧找答案app
您可能感兴趣的
1一个循环队列Q最多可存储m个元素，已知其头尾指针分别是：front和rear，则判定该循环队列为满的条件是(&&&&&)。A.Q．rear—Q．front==mB.Q．rear!=Q．frontC.Q．front=(Q．rear+1)％mD.Q．front==Q．rear％m+12某二叉树的先序和后序序列正好相反，则该二叉树一定是(&&&&&)。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子3对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，为实现编号可采用的遍历是 (&&&&&)。A.先序B.中序C.后序D.从根开始按层次遍历4一棵哈夫曼树共有9个结点，则其叶子结点的个数为(&&&&&)。A.4B.5C.6D.7数据结构之中缀表达式转后缀表达式_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构之中缀表达式转后缀表达式
&&数据结构之中缀表达式转后缀表达式
阅读已结束，下载文档到电脑
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩8页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢用户名：wawlian
文章数：50
访问量：33058
注册日期：
阅读量：1297
阅读量：3317
阅读量：582951
阅读量：467913
51CTO推荐博文
&&& 我们在数学中常见的计算式，例如2+（3*4）叫做中缀表达式。表达式中涉及到了多个运算符，而运算符之间是有优先级的。计算机在计算并且处理这种表达式时，需要将中缀表达式转换成后缀表达式，然后再进行计算。
&&& 中缀表达式转后缀表达式遵循以下原则：
&&& 1.遇到操作数，直接输出；
&&& 2.栈为空时，遇到运算符，入栈；
&&& 3.遇到左括号，将其入栈；
&&& 4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；
&&& 5.遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈；
&&& 6.最终将栈中的元素依次出栈，输出。
&&& 经过上面的步骤，得到的输出既是转换得到的后缀表达式。
&&& 举例：a+b*c+(d*e+f)*g&&& ---------& abc*+de*f+g*+
遇到a，直接输出：
遇到+，此时栈为空，入栈：
遇到b，直接输出：
遇到*,优先级大于栈顶符号优先级，入栈：
遇到c，输出：
遇到+，目前站内的*与+优先级都大于或等于它，因此将栈内的*，+依次弹出并且输出，并且将遇到的这个+入栈：
遇到(,将其入栈：
遇到d，直接输出：
遇到*，由于*的优先级高于处在栈中的(，因此*入栈：
遇到e，直接输出：
遇到+，栈顶的*优先级高于+，但是栈内的(低于+，将*出栈输出，+入栈：
遇到f，直接输出：
遇到),弹出栈顶元素并且输出，直到弹出(才结束，在这里也就是弹出+输出，弹出(不输出：
遇到*，优先级高于栈顶+，将*入栈：
遇到g，直接输出：
此时已经没有新的字符了，依次出栈并输出操作直到栈为空：
明白了这个过程，现在就需要用代码实现了。对于各种运算符的优先级，可以使用整数来表示运算符的级别。可以定义一个函数来返回各种符号的优先级数字：
&&&&&&&int&GetPrecedence(char&c,int&flag)&{&&&&&if(c=='+'&||&c=='-')&&&&&{&&&&&&&&&return&1;&&&&&}&&&&&else&if(c=='*'&||&c=='/')&&&&&{&&&&&&&&&return&2;&&&&&}&&&&&else&if(c=='('&&&&flag==0)&&&&&{&&&&&&&&&return&0;&&&&&}&&&&&else&if(c=='('&&&&flag==1)&&&&&{&&&&&&&&&return&3;&&&&&}&&&&&else&&&&&{&&&&&&&&&fprintf(stderr,&Input&char&is&invalid!\n&);&&&&&&&&&return&-1;&&&&&}&}&
&还可以定义一个函数来判断当前遇到的是运算符还是操作数：
&&&&int&IsOperator(char&c)&{&&&&&if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')')&&&&&{&&&&&&&&&return&0;&&&&&}&&&&&else&&&&&{&&&&&&&&&return&1;&&&&&}&}&
完整代码：
#include&&stdio.h&&#include&&stdlib.h&&#define&ElementType&char&&typedef&struct&Node&*PtrToN&typedef&PtrToNode&S&typedef&struct&Node&{&&&&&ElementType&E&&&&&PtrToNode&N&};&&int&IsEmpty(Stack&S);&Stack&CreateStack();&void&DisposeStack(Stack&S);&void&MakeEmpty(Stack&S);&void&Push(ElementType&X,Stack&S);&ElementType&Top(Stack&S);&void&Pop(Stack&S);&&&int&IsEmpty(Stack&S)&{&&&&&return&S-&Next&==&NULL;&}&&Stack&CreateStack()&{&&&&&Stack&S&=&malloc(sizeof(struct&Node));&&&&&if(S&==&NULL)&&&&&{&&&&&&&&&printf(&No&enough&memory!&);&&&&&&&&&return&NULL;&&&&&}&&&&&S-&Next&=&NULL;&&&&&MakeEmpty(S);&&&&&return&S;&}&&void&MakeEmpty(Stack&S)&{&&&&&if(S&==&NULL)&&&&&{&&&&&&&&&printf(&Use&CreateStack&First!&);&&&&&}&&&&&else&&&&&{&&&&&&&&&while(!IsEmpty(S))&&&&&&&&&{&&&&&&&&&&&&&Pop(S);&&&&&&&&&}&&&&&}&}&&void&Push(ElementType&X,Stack&S)&{&&&&&PtrToNode&T&&&&&Tmp&=&malloc(sizeof(struct&Node));&&&&&if(Tmp&!=&NULL)&&&&&{&&&&&&&&&Tmp-&Element&=&X;&&&&&&&&&Tmp-&Next&=&S-&N&&&&&&&&&S-&Next&=&T&&&&&}&&&&&else&&&&&{&&&&&&&&&printf(&Out&of&space!&);&&&&&}&}&&void&Pop(Stack&S)&{&&&&&&&&&&if(IsEmpty(S))&&&&&{&&&&&&&&&printf(&The&Stack&is&Empty!&);&&&&&}&&&&&else&&&&&{&&&&&&&&&PtrToNode&Tmp&=&S-&N&&&&&&&&&S-&Next&=&Tmp-&N&&&&&&&&&free(Tmp);&&&&&}&}&&ElementType&Top(Stack&S)&{&&&&&if(IsEmpty(S))&&&&&{&&&&&&&&&printf(&The&stack&is&empty!&);&&&&&&&&&return&0;&&&&&}&&&&&else&&&&&{&&&&&&&&&return&S-&Next-&E&&&&&}&}&&&&&&&&&int&GetPrecedence(char&c,int&flag)&{&&&&&if(c=='+'&||&c=='-')&&&&&{&&&&&&&&&return&1;&&&&&}&&&&&else&if(c=='*'&||&c=='/')&&&&&{&&&&&&&&&return&2;&&&&&}&&&&&else&if(c=='('&&&&flag==0)&&&&&{&&&&&&&&&return&0;&&&&&}&&&&&else&if(c=='('&&&&flag==1)&&&&&{&&&&&&&&&return&3;&&&&&}&&&&&else&&&&&{&&&&&&&&&fprintf(stderr,&Input&char&is&invalid!\n&);&&&&&&&&&return&-1;&&&&&}&}&&&&&&int&IsOperator(char&c)&{&&&&&if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')')&&&&&{&&&&&&&&&return&0;&&&&&}&&&&&else&&&&&{&&&&&&&&&return&1;&&&&&}&}&&char&Output[50];&&char*&InfixToPostfix(char&*ch,Stack&S)&{&&&&&&&&&&int&index=0;&&&&&char&c;&&&&&while((c=*ch)&!=&'\0')&&&&&{&&&&&&&&&&&&&&&&&&if(IsOperator(c)==1)&&&&&&&&&{&&&&&&&&&&&&&Output[index++]&=&c;&&&&&&&&&&&&&ch++;&&&&&&&&&}&&&&&&&&&&&&&&&&&&else&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&&&&&&&if(IsEmpty(S))&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&Push(c,S);&&&&&&&&&&&&&&&&&ch++;&&&&&&&&&&&&&&&&&continue;&&&&&&&&&&&&&}&&&&&&&&&&&&&else&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&if(c==')')&&&&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&&while(!IsEmpty(S)&&&&Top(S)&!=&'(')&&&&&&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&&&&&&Output[index++]&=&Top(S);&&&&&&&&&&&&&&&&&&&&&&&&&Pop(S);&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&Pop(S);&&&&&&&&&&&&&&&&&&&&&ch++;&&&&&&&&&&&&&&&&&&&&&continue;&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&&int&outPrecedence&=&GetPrecedence(c,1);&&&&&&&&&&&&&&&&&&&&&while(!IsEmpty(S)&&&&GetPrecedence(Top(S),0)&&=&outPrecedence)&&&&&&&&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&&&&&&Output[index++]&=&Top(S);&&&&&&&&&&&&&&&&&&&&&&&&&Pop(S);&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&Push(c,S);&&&&&&&&&&&&&&&&&&&&&ch++;&&&&&&&&&&&&&&&&&&&&&continue;&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&}&&&&&&&&&}&&&&&}&&&&&while(!IsEmpty(S))&&&&&{&&&&&&&&&Output[index++]&=&Top(S);&&&&&&&&&Pop(S);&&&&&}&&&&&Output[index]&=&'\0';&&&&&return&O&}&&&&int&main(void)&{&&&&&Stack&S&=&CreateStack();&&&&&char&*charSequence&=&&1+2*3+(4*5+6)*7&;&&&&&char&&&&&&char&*out&=&InfixToPostfix(charSequence,S);&&&&&&&&&&&&&&&while((tmp=*out)!='\0')&&&&&{&&&&&&&&&printf(&%c&&,tmp);&&&&&&&&&out++;&&&&&}&&&&&printf(&\n&);&&&&&return&0;&}&
&本文出自 “” 博客，请务必保留此出处
了这篇文章
类别：┆阅读(0)┆评论(0)博客分类：
后缀表达式又叫逆波兰表达式。那么如何讲中缀表达式转化为后缀表达式呢？
比如已知中缀表达式a+b*c+(d*e+f)*g，如何将其转化为后缀表达式abc*+de*f+g*+呢？有4个基本原则。
1. 当读到操作数时，立即输出（由后缀表达式的形式明显可以看出，操作数的输出优先级要比操作符要高）；当读到操作符时，并不立即输出，而是将其存于堆栈中。
2. 如果见到右括号，那么将栈元素弹出，直到遇到左括号。但是左括号只是弹出，并不输出。
3. 如果见到其他符号，我们将栈中输出优先级更高（或者相同）的符号全部弹出。然后将此符号入栈。（即把别人挤出去之后，自己入栈）
4. 强调一下，比如见到符号“+”，如果栈顶有符号“-”。优先级相同。需要将“-”弹出，“+”入栈。优先级相同也要弹出！
下面举个例子，写出a+b*c+(d*e+f)*g的后缀表达式。
（画图表示不方便，我们用下表表示转换过程）
首先读到a，因为a属于操作数，直接输出
读到“*”号。栈顶符号“+”号的优先级不比“*”号的优先级高，也不是不相同。故将“*”入栈。
读“+”号，因为栈顶符号“*”比读到的“+”优先级高，栈顶符号“+”与独到的“+”优先级相同，故“*”和“+”都弹出。将刚读到的“+”号入栈。
读到“（”，将“）“后的栈顶元素全部输出。
输入串遍历完毕，将栈中剩余元素全部弹出。
ErinToJerry
浏览: 36152 次
来自: 武汉
牛刀了。不都单片机或者中规模时序芯片做吗。
端口地址译码（DA地址线）后选中某端口，然后进行数据传输（DB ...
dian的数据结构课是精华。旁听了好多次
ErinToJerry 写道spyker 写道失恋就是吃饭
没 ...
spyker 写道失恋就是吃饭没失恋啊。这还没恋呢。嘿~
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'}