中缀表达式转换为后缀表达式
在表达式计算中，第一要做的就是讲中缀表达式转换成后缀表达式
所采用的方式是，扫描中缀表达式，检测每个中缀表达式的元素
如果是操作数，则将其加入到输出的后缀表达式中
如果是操作符，需要对其分析，设定一个操作符栈，
·如果一开始操作符栈为空，则将该操作符压栈
·这里涉及左括号的两个优先级，即栈外优先级和栈内优先级，如果左括号在栈外，则其优先级最高，直接将其压入到操作符栈中，如果左括号在栈内，则其优先级很低，只有在碰到右括号的时候才会弹栈，遇到其他运算符时，直接当其他运算符压栈。
·这里涉及操作符优先级问题，+ - * / % 这里的优先级相对于压操作符栈的优先级。即检测当前操作符与栈顶的操作符优先级，如果当前操作符优先级高于栈顶操作符优先级，需要将当前操作符压栈，如果当前操作符优先级小于或等于栈顶操作符优先级，则将栈顶操作符出栈，然后再次检测下一个栈顶操作符的优先级与当前操作符优先级关系。
·对于有左括号和右括号的情况，需要对其做特殊分析。左括号会被压入栈中，右括号不会。如果当前元素时左括号，由于其栈外优先级最高，可以直接将其压入栈中，如果栈顶优先级是左括号，并且当前操作符是一般操作符，则直接将当前操作符压入栈中，如果当前操作符是右括号，则直接将栈顶的左括号出栈。
·中缀表达式和后缀表达式的不同是操作符的相对位置存在变化，当然后缀表达式不会出现括号，也就是后缀表达式中隐式包含了操作符的优先级。另外中缀和后缀表达式中的操作数相对顺序是一致的，在转换的过程中，当当前中缀表达式中的元素时操作数时，直接将其添加到输出后缀表达式中就可以。
这里利用的栈是操作符栈
在计算后缀表达式的过程中，利用的栈是操作数栈
从中缀表达式转换为后缀表达式也是一遍扫描中缀表达式即可，当然中间涉及对操作符栈的操作。
修正：( ( 1 + 2 ) * 3 + ( 1 + 10 ) ) / 2 ， ( ( ( 1 + 2 + 3 ) ) ) 的情形。要时刻考虑到括号的特殊性，左括号的栈内优先级和栈外优先级的区别。对于左括号和右括号的主动入栈和出栈以及其他操作符的相对于其入栈和出栈决策要考虑清楚。
实现：
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <stack>
5 #include <map>
6 using namespace std;
7
8 map<string, int> operatorPriors;
9
10 void getInfix(vector<string>& infix)
11 {
12 infix.clear();
13 string tmp;
14 while (cin >> tmp)
15 {
16 infix.push_back(tmp);
17 }
18 }
19
20 void init()
21 {
22 operatorPriors["+"] = 10;
23 operatorPriors["-"] = 10;
24 operatorPriors["*"] = 20;
25 operatorPriors["/"] = 20;
26 operatorPriors["%"] = 20;
27 operatorPriors["("] = 30;
28 operatorPriors[")"] = 0;
29 }
30
31 bool prior(const string& op1, const string& op2)
32 {
33 return operatorPriors[op1] > operatorPriors[op2];
34 }
35
36 bool isOperator(const string& s)
37 {
38 return operatorPriors.find(s) != operatorPriors.end();
39 }
40
41 void print(stack<string> operators)
42 {
43 while (!operators.empty())
44 {
45 cout << operators.top() << ' ';
46 operators.pop();
47 }
48 cout << endl;
49 }
50
51 const vector<string>& infixToPostfix(vector<string>& postfix, const vector<string>& infix)
52 {
53 postfix.clear();
54 stack<string> operators;
55 for (vector<string>::size_type i = 0; i != infix.size(); ++i)
56 {
57 if (isOperator(infix[i]))
58 {
59 if (operators.empty())
60 {
61 operators.push(infix[i]);
62 }
63 else if (operators.top() == "(" && infix[i] != ")" || prior(infix[i], operators.top()))
64 {
65 operators.push(infix[i]);
66 }
67 else
68 {
69 if (infix[i] == ")")
70 {
71 while (operators.top() != "(")
72 {
73 postfix.push_back(operators.top());
74 operators.pop();
75 }
76 operators.pop();
77 }
78 else
79 {
80 postfix.push_back(operators.top());
81 operators.pop();
82 while (!operators.empty() && !prior(infix[i], operators.top()) && operators.top() != "(")
83 {
84 postfix.push_back(operators.top());
85 operators.pop();
86 }
87
88 operators.push(infix[i]);
89 }
90 }
91 }
92 else
93 {
94 postfix.push_back(infix[i]);
95 }
96 }
97 while (!operators.empty())
98 {
99 postfix.push_back(operators.top());
100 operators.pop();
101 }
102 return postfix;
103 }
104
105 int main()
106 {
107 init();
108 vector<string> infix;
109 vector<string> postfix;
110 getInfix(infix);
111 infixToPostfix(postfix, infix);
112 for (vector<string>::size_type i = 0; i != postfix.size(); ++i)
113 {
114 cout << postfix[i] << ' ';
115 }
116 cout << endl;
117 return 0;
118 }
posted on 2011-06-29 01:07
unixfy 阅读(566)
评论(0) 编辑 收藏 引用