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