中綴表達式轉換為后綴表達式
在表達式計算中，第一要做的就是講中綴表達式轉換成后綴表達式
所采用的方式是，掃描中綴表達式，檢測每個中綴表達式的元素
如果是操作數，則將其加入到輸出的后綴表達式中
如果是操作符，需要對其分析，設定一個操作符棧，
·如果一開始操作符棧為空，則將該操作符壓棧
·這里涉及左括號的兩個優(yōu)先級，即棧外優(yōu)先級和棧內優(yōu)先級，如果左括號在棧外，則其優(yōu)先級最高，直接將其壓入到操作符棧中，如果左括號在棧內，則其優(yōu)先級很低，只有在碰到右括號的時候才會彈棧，遇到其他運算符時，直接當其他運算符壓棧。
·這里涉及操作符優(yōu)先級問題，+ - * / % 這里的優(yōu)先級相對于壓操作符棧的優(yōu)先級。即檢測當前操作符與棧頂的操作符優(yōu)先級，如果當前操作符優(yōu)先級高于棧頂操作符優(yōu)先級，需要將當前操作符壓棧，如果當前操作符優(yōu)先級小于或等于棧頂操作符優(yōu)先級，則將棧頂操作符出棧，然后再次檢測下一個棧頂操作符的優(yōu)先級與當前操作符優(yōu)先級關系。
·對于有左括號和右括號的情況，需要對其做特殊分析。左括號會被壓入棧中，右括號不會。如果當前元素時左括號，由于其棧外優(yōu)先級最高，可以直接將其壓入棧中，如果棧頂優(yōu)先級是左括號，并且當前操作符是一般操作符，則直接將當前操作符壓入棧中，如果當前操作符是右括號，則直接將棧頂的左括號出棧。
·中綴表達式和后綴表達式的不同是操作符的相對位置存在變化，當然后綴表達式不會出現括號，也就是后綴表達式中隱式包含了操作符的優(yōu)先級。另外中綴和后綴表達式中的操作數相對順序是一致的，在轉換的過程中，當當前中綴表達式中的元素時操作數時，直接將其添加到輸出后綴表達式中就可以。
這里利用的棧是操作符棧
在計算后綴表達式的過程中，利用的棧是操作數棧
從中綴表達式轉換為后綴表達式也是一遍掃描中綴表達式即可，當然中間涉及對操作符棧的操作。
修正：( ( 1 + 2 ) * 3 + ( 1 + 10 ) ) / 2 ， ( ( ( 1 + 2 + 3 ) ) ) 的情形。要時刻考慮到括號的特殊性，左括號的棧內優(yōu)先級和棧外優(yōu)先級的區(qū)別。對于左括號和右括號的主動入棧和出棧以及其他操作符的相對于其入棧和出棧決策要考慮清楚。
實現：
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 閱讀(574)
評論(0) 編輯 收藏 引用