【C++】朝花夕拾——中缀转后缀

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

对于简单的四则运算而言，后缀表达式可以通过使用栈(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 }