使用棧Stack對整數數值的運算表達式字符串進行運算C#，
這裡如果對於形如字符串“((6+（（7+8）-9）*9+8/2)-3)/2”的運算表達式進行運算。接觸過此類的同學知道這種存在著運算符優先級的表達式，不能直接從左到右進行運算，我們使用OperandStack操作數棧和OperatorStack操作符棧，對操作符進行比較，確定優先級後，取出操作數進行運算。
算法思想如下：
1.首先確定操作的符的優先級，*、/大於+、-，（大於*、/,*、/或者+、-一起時，排在前面的運算符優先，）的優先級最小，且）與（相遇時抵消
2.從左到右遍歷字符串，每次遍歷一個字符，設置數字臨時存儲變量OperandTemp
①當遇到操作符時， 如果OperandTemp有數值，把數字壓入到OperandStack中
②循環OperatorStack，直到OperatorStack沒值為止，然後比較這個操作符和OperatorStack頂部的運算符進行比較，如果此操作符運算優先級高，將此運算符壓入棧，退出循環；如果此操作符運算優先級低，則將OperatorStack棧頂的運算符取出ope1，從OperandStack中取出頂部的兩個數值a1（先出棧）和a2，注意首先出棧的做第二個操作數，則進行
a2 ope1 a1；求得結果壓人OperandStack中；如果此操作符是）遇到（時，將OperatorStack棧中的（消除
③循環到最後會剩余2中情況，即OperatorStack中剩1個運算符，剩余兩個運算符，且最後一個運算符優先級高，則讀取最後一個數字和OperandStack頂的數字進行操作運算，求得結果，再運算。
以字符串“((6+（（7+8）-9）*9+8/2)-3)/2”為例，算法的運算過程是，先將（（壓入OperatorStack變為【（（】，將6壓入OperandStack【6】，到+，由於（不參與運算，則將+壓入
OperatorStack【（（+】，下一個字符（的優先級大於OperatorStack頂的+，則將（壓入OperatorStack【（（+（】，下一個（壓入OperatorStack【（（+（（】，7壓入OperandStack【6,7】，下一個+同理壓入
OperatorStack【（（+（（+】，8壓入OperandStack【6,7,8】，下一個）優先級小於OperatorStack頂部的+，則取出OperandStack頂部的8和7和OperatorStack頂部的+，運算得15壓入OperandStack，繼續比較）和OperatorStack頂的（，優先級相同，同時消去（，此時OperatorStack為【（（+（】，OperandStack位【6,15】，下一個字符-小於（，入棧【（（+（—】，9入棧OperandStack為【6,15,9】；下一個），取出-和15,9進行運算得6，入棧OperandStack【6,6】；）消去棧頂（OperatorStack為【（（+】；下一個*同理，OperandStack【6,6】，OperatorStack為【（（+*】；下一個9入棧OperandStack【6,6，9】；下一個+，優先級小於*，則6*9=54入棧，OperandStack【6,54】，OperatorStack為【（（+】；下一個+，優先級小，則取出棧頂+6+54=60入棧OperandStack【60】，壓入此運算符+OperatorStack為【（（+】；下一個8入棧OperandStack【60，8】；下一個/,優先級大入棧，2入棧，則OperatorStack為【（（+/】,OperandStack【60，8,2】;下一個）優先級小，則
OperatorStack為【（（+】,OperandStack【60，4】=》OperatorStack為【（】,OperandStack【64】；下一個-入棧，3入棧OperatorStack為【（-】,OperandStack【64，3】；下一個），則64-3=61入棧，OperatorStack為【空】,OperandStack【61】；下一個/入棧，2入棧，OperatorStack為【/】,OperandStack【61,2】;此為剩下一操作符的情況，最後運算得到結果：61/2=30.5
實現代碼如下：
![]()
1 static char[] Operators = new char[] { '+', '-', '*', '/', '(', ')' };
2 static void Main(string[] args)
3 {
4 float a = EvaluateExpression("10+(80*3+(6+7))*2");
5 Console.WriteLine(a);
6 Console.ReadKey();
7
8 }
9 /// <summary>
10 /// 初始化運算符優先級
11 /// </summary>
12 /// <param name="a"></param>
13 /// <param name="b"></param>
14 /// <returns></returns>
15 static char InitPriorities(char a, char b)
16 {
17 int aIndex = -1;
18 int bIndex = -1;
19 for (int i = 0; i < Operators.Length; i++)
20 {
21 if (Operators[i] == a)
22 aIndex = i;
23 if (Operators[i] == b)
24 bIndex = i;
25
26 }
27 char[,] Priorities = new char[6, 6] {{'>','>','<','<','<','>'},
28 {'>','>','<','<','<','>'},
29 {'>','>','>','>','<','>'},
30 {'>','>','>','>','<','>'},
31 {'<','<','<','<','<','='},
32 {'?','?','?','?','?','?'}};
33 return Priorities[aIndex, bIndex];
34 }
35 static float Calculate(float Operand1, float Operand2, char Operator)
36 {
37 float Ret = 0;
38 if (Operator == '+')
39 {
40 Ret = Operand1 + Operand2;
41 }
42 else if (Operator == '-')
43 {
44 Ret = Operand1 - Operand2;
45 }
46 else if (Operator == '*')
47 {
48 Ret = Operand1 * Operand2;
49 }
50 else if (Operator == '/')
51 {
52 Ret = Operand1 / Operand2;
53 }
54
55 return Ret;
56 }
57 static float EvaluateExpression(string str)
58 {
59 Stack<float> OperandStack = new Stack<float>(); // 操作數棧，
60 Stack<char> OperatorStack = new Stack<char>(); // 操作符棧
61 float OperandTemp = 0;
62
63 char LastOperator = '0'; // 記錄最後遇到的操作符
64
65 for (int i = 0, size = str.Length; i < size; ++i)
66 {
67 char ch = str[i];
68
69 if ('0' <= ch && ch <= '9')
70 { // 讀取一個操作數
71 OperandTemp = OperandTemp * 10 + ch - '0';
72 }
73 else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' ||
74 ch == '(' || ch == ')')
75 {
76 // 有2種情況 是沒有操作數需要入棧保存的。
77 // 1 當前操作符是 “(”。（的左邊的操作符已經負責操作數入棧了。
78 // 2 上一次遇到的操作符是“）”。）本身會負責操作數入棧，）後面緊跟的操作符不需要再負責操作數入棧。
79 if (ch != '(' && LastOperator != ')')
80 {
81 // 遇到一個操作符後，意味著之前讀取的操作數已經結束。保存操作數。
82 OperandStack.Push(OperandTemp);
83 // 清空，為讀取下一個操作符做准備。
84 OperandTemp = 0;
85 }
86
87 // 當前遇到的操作符作為操作符2，將和之前遇到的操作符（作為操作符1）進行優先級比較
88 char Opt2 = ch;
89
90 for (; OperatorStack.Count > 0; )
91 {
92 // 比較當前遇到的操作符和上一次遇到的操作符(頂部的操作符)的優先級
93 char Opt1 = OperatorStack.Peek();
94 char CompareRet = InitPriorities(Opt1, Opt2);
95 if (CompareRet == '>')
96 { // 如果操作符1 大於 操作符2 那麼，操作符1應該先計算
97
98 // 取出之前保存的操作數2
99 float Operand2 = OperandStack.Pop();
100
101 // 取出之前保存的操作數1
102 float Operand1 = OperandStack.Pop();
103
104 // 取出之前保存的操作符。當前計算這個操作符，計算完成後，消除該操作符，就沒必要保存了。
105 OperatorStack.Pop();
106
107 // 二元操作符計算。並把計算結果保存。
108 float Ret = Calculate(Operand1, Operand2, Opt1);
109 OperandStack.Push(Ret);
110 }
111 else if (CompareRet == '<')
112 { // 如果操作符1 小於 操作符2，說明 操作符1 和 操作符2 當前都不能進行計算，
113 // 退出循環，記錄操作符。
114 break;
115 }
116 else if (CompareRet == '=')
117 {
118 // 操作符相等的情況，只有操作符2是“）”，操作數1是“（”的情況，
119 // 彈出原先保存的操作符“（”，意味著“（”，“）”已經互相消掉，括號內容已經計算完畢
120 OperatorStack.Pop();
121 break;
122 }
123
124 } // end for
125
126 // 保存當前遇到操作符，當前操作符還缺少右操作數，要讀完右操作數才能計算。
127 if (Opt2 != ')')
128 {
129 OperatorStack.Push(Opt2);
130 }
131
132 LastOperator = Opt2;
133 }
134
135 } // end for
136
137
138 /*
139 上面的 for 會一面遍歷表達式一面計算，如果可以計算的話。
140 當遍歷完成後，並不代表整個表達式計算完成了。而會有2種情況：
141 1.剩余1個運算符。
142 2.剩余2個運算符，且運算符1 小於 運算符2。這種情況，在上面的遍歷過程中是不能進行計算的，所以才會被遺留下來。
143 到這裡，已經不需要進行優先級比較了。情況1和情況2，都是循環取出最後讀入的操作符進行運算。
144 */
145 if (LastOperator != ')')
146 {
147 OperandStack.Push(OperandTemp);
148 }
149 for (; OperatorStack.Count > 0; )
150 {
151 // 取出之前保存的操作數2
152 float Operand2 = OperandStack.Pop();
153
154 // 取出之前保存的操作數1
155 float Operand1 = OperandStack.Pop();
156
157 // 取出末端一個操作符
158 char Opt = OperatorStack.Pop();
159
160 // 二元操作符計算。
161 float Ret = Calculate(Operand1, Operand2, Opt);
162 OperandStack.Push(Ret);
163 }
164
165 return OperandStack.Peek();
166 }
View Code
