想做一个有关树的操作,就想了解下后缀表达式,下面的代码来自百度百科
1 //============================================================================
2 // Name : 后缀表达式.cpp
3 // Author :
4 // Version :
5 // Copyright : Your copyright notice
6 // Description : Hello World in C++, Ansi-style
7 //============================================================================
8
9 #include <stack>
10 #include <vector>
11 #include <iostream>
12 #include <algorithm>
13 using namespace std;
14 bool isOper(char c)
15 //判断是否为操作符
16 {
17 if ((c== '+')||(c== '-')||(c== '*')||(c== '/')||(c== '(')||(c== ')'))
18 return true;
19 return false;
20 }
21 bool isHigh(char top_op,char InfixExp_op)
22 //判断操作符的优先级
23 //top_op为栈顶操作符
24 //InfixExp_op为当前读入操作符
25 //如果栈顶操作符优先级高,则弹出栈顶操作符
26 //如果栈顶操作符优先级低,则压入当前读入操作符
27 {
28 if ((top_op== '+')&&(InfixExp_op== '+')) return true;
29 if ((top_op== '+')&&(InfixExp_op== '-')) return true;
30 if ((top_op== '-')&&(InfixExp_op== '+')) return true;
31 if ((top_op== '-')&&(InfixExp_op== '-')) return true;
32 if ((top_op== '*')&&(InfixExp_op== '+')) return true;
33 if ((top_op== '*')&&(InfixExp_op== '-')) return true;
34 if ((top_op== '*')&&(InfixExp_op== '*')) return true;
35 if ((top_op== '*')&&(InfixExp_op== '/')) return true;
36 if ((top_op== '/')&&(InfixExp_op== '+')) return true;
37 if ((top_op== '/')&&(InfixExp_op== '-')) return true;
38 if ((top_op== '/')&&(InfixExp_op== '*')) return true;
39 if ((top_op== '/')&&(InfixExp_op== '/')) return true;
40 if (InfixExp_op== ')') return true;
41 return false;
42 }
43 void input(vector <char> *InfixExp)
44 {
45 char c;
46 cin>> c;
47 while(c!= '$')
48 {
49 InfixExp-> push_back(c);//向末尾添加一个值为c的元素
50 cin>> c;
51 }
52 }
53 void output(vector <char> *postfixExp)
54 {
55 vector <char> ::iterator postfixExp_it;//后缀表达式迭代器
56 for(postfixExp_it=postfixExp-> begin();postfixExp_it!=postfixExp-> end();postfixExp_it++)
57 cout<<*postfixExp_it << " ";
58 cout<<endl;
59 }
60 void output2(vector <char> *postfixExp)
61 //不输出括号
62 //如果表达式中括号不配对
63 //则可能有多余的括号未弹出
64 {
65 vector <char> ::iterator postfixExp_it;//后缀表达式迭代器
66 for(postfixExp_it=postfixExp-> begin();postfixExp_it!=postfixExp-> end();postfixExp_it++)
67 {
68 if ((*postfixExp_it!= '(')&&(*postfixExp_it!= ')'))//不是括号就输出
69 cout <<*postfixExp_it << " ";
70 }
71 cout <<endl;
72 }
73 int main(){
74 stack <char> mystack;
75 vector <char> InfixExp;//中缀表达式
76 vector <char> ::iterator InfixExp_it;//中缀表达式迭代器
77 vector <char> postfixExp;//后缀表达式
78 do
79 {
80 cout<< "Please input a formula, ended by $: " <<endl;
81 input(&InfixExp);
82 //输入表达式
83 output(&InfixExp);
84 //输出刚刚输入的表达式
85 for(InfixExp_it=InfixExp.begin();InfixExp_it!=InfixExp.end();InfixExp_it++)
86 {
87 if (!isOper(*InfixExp_it))
88 //不是操作符+-*/(),操作数,则直接输出
89 postfixExp.push_back(*InfixExp_it);
90 else
91 //是操作符
92 {
93 if (mystack.empty())
94 //栈为空,压入操作符
95 mystack.push(*InfixExp_it);
96 else if(isHigh(mystack.top(),*InfixExp_it))
97 //栈顶操作符优先,比如栈顶为*,当前操作符为+,则弹出*
98 {
99 if (*InfixExp_it!= ')')
100 //非闭括号
101 //弹出栈中操作符直到栈顶操作数优先级低于当前读入操作数
102 //压入当前读入操作符
103 {
104 do
105 {
106 postfixExp.push_back(mystack.top());
107 mystack.pop();
108 }while((!mystack.empty())&&(isHigh(mystack.top(),*InfixExp_it)));
109 mystack.push(*InfixExp_it);
110 }
111 else
112 //闭括号
113 {
114 while((!mystack.empty())&&(mystack.top()!= '('))
115 //弹出直到开括号
116 {
117 postfixExp.push_back(mystack.top());
118 mystack.pop();
119 }
120 if ((!mystack.empty())&&(mystack.top()== '('))
121 mystack.pop();
122 //弹出开括号
123 }
124 }
125 else if(!isHigh(mystack.top(),*InfixExp_it))
126 //中缀表达式中操作符优先
127 //比如栈顶为+,而当前读入*
128 {
129 mystack.push(*InfixExp_it);
130 //压入当前读入操作符
131 }
132 }
133 }
134 while(!mystack.empty())
135 //把栈中剩余的操作符依次弹出
136 {
137 postfixExp.push_back(mystack.top());
138 mystack.pop();
139 }
140 output2(&postfixExp);
141 while(!mystack.empty())
142 mystack.pop();
143 InfixExp.clear();
144 postfixExp.clear();
145 //清空栈、中缀表达式和后缀表达式
146 }while(true);
147 }
运行结果:
原文链接: https://www.cnblogs.com/menglei/archive/2012/11/05/2754922.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/68289
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!