对于简单的四则运算而言,后缀表达式可以通过使用栈(stack)快速算出结果
==================================我是分割线====================================
后缀的定义:
e.g. 2 + 3 -> 2 3 +
2 + 3 * 4 -> 2 3 4 * +
应用栈来计算后缀表达式:
e.g. 后缀表达式 6 5 2 3 + 8 * + 3 + *
遍历: 6 push(6) stack: 6
5 push(5) stack: 6 5
2 push(2) stack: 6 5 2
3 push(3) stack: 6 5 2 3
- pop、pop 2、 3出栈,操作 ans = 2 + 3; push(ans) stack: 6 5 5
8 push(8) stack: 6 5 5 8
-
pop、pop 5、 8出栈,操作 ans = 5 * 8; push(ans) stack: 6 5 40
-
pop、pop 5、 40出栈,操作 ans = 5 + 40; push(ans) stack: 6 45
3 push(3) stack: 6 45 3
-
pop、pop 45、 3出栈,操作 ans = 45 + 3; push(ans) stack: 6 48
-
pop、pop 6、 48出栈,操作 ans = 6 * 48; push(ans) stack: 288
把中缀表达式转化成后缀表达式:
设定: 优先级 ‘(’ > ‘*’ = ‘/’ > ‘+’ = ‘-’
①读取输入队列的字符,判断是数字还是符号+-*/()
②若是数字,放到输出队列
③若是‘)’,则把stack中的符号一一弹出到输出队列,直到遇到第一个‘(’,且‘(’不用放到输出队列
④若是其他符号+-*/(,则把栈中元素弹出,直到发现优先级更低的符号或者‘(’为止。'('只有在遇到‘)’时才弹出
代码实现:
1 //2016-03-16
2 //中缀转后缀
3
4 //局限性:输入合法、数字为0~9的范围
5 #include <iostream>
6 #include <string>
7 #include <stack>
8
9 using namespace std;
10
11 int main() {
12 string input, output;
13 stack<char> operators;
14 while (cin >> input) {
15 if (input == "0") break;
16 output.clear();
17 for (int i = 0; i < input.size(); i++) {
18 char ch = input[i];
19 if (ch >= '0' && ch <= '9') output.push_back(ch);
20 else if (ch == '+' || ch == '-') {
21 while (!operators.empty() && (operators.top() == '*' || operators.top() == '/' || operators.top() == '-' || operators.top() == '+')) {
22 output.push_back(operators.top());
23 operators.pop();
24 }
25 operators.push(ch);
26 }
27 else if (ch == '*' || ch == '/') {
28 while (!operators.empty() && (operators.top() == '*' || operators.top() == '/')) {
29 output.push_back(operators.top());
30 operators.pop();
31 }
32 operators.push(ch);
33 }
34 else if (ch == ')') {
35 while (operators.top() != '(' && !operators.empty()) {
36 output.push_back(operators.top());
37 operators.pop();
38 }
39 operators.pop();
40 }
41 else if (ch == '(') {
42 operators.push(ch);
43 }
44 }
45 while (!operators.empty()) {
46 output.push_back(operators.top());
47 operators.pop();
48 }
49 cout << "output : " << output << endl;
50 }
51 return 0;
52 }
测试:
局限性:(不够健壮)
①只实现了0~9的数字输入,若是两位以上的数字还需要做字符判断(前一个字符是否是数字,若是,则当前字符和前一位同属一个整数)
②没有做最后的结果计算,因为还是字符串,如果需要,则要做字符到整型的转换判断。
③没有异常检测(假设所有输入都合法,不合法的输入会直接导致错误输出)
一些bugs:
①stack容器内没有clear();
②判断条件while (!operators.empty() && (operators.top() == '*' || operators.top() == '/'))中必须先判断!operators.empty()
否则先判断(operators.top() == '*' || operators.top() == '/')事实上是会做top()的读取操作,此时栈若为空,就会runtime error
原文链接: https://www.cnblogs.com/cheermyang/p/5283963.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/230285
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!