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