利用堆棧解析算術(shù)表達(dá)式一：基本過(guò)程1 本文目標(biāo)
大致的規(guī)律是，一元運(yùn)算符 > 二元運(yùn)算符 > 多元運(yùn)算符。 4 利用堆棧解析算術(shù)表達(dá)式的過(guò)程 中綴表達(dá)式翻譯成后綴表達(dá)式的方法如下： （1）從右向左依次取得數(shù)據(jù)ch。 （2）如果ch是操作數(shù)，直接輸出。 （3）如果ch是運(yùn)算符（含左右括號(hào)），則： a：如果ch = '('，放入堆棧。 b：如果ch = ')'，依次輸出堆棧中的運(yùn)算符，直到遇到'('為止。 c：如果ch不是')'或者'('，那么就和堆棧頂點(diǎn)位置的運(yùn)算符top做優(yōu)先級(jí)比較。 1：如果ch優(yōu)先級(jí)比top高，那么將ch放入堆棧。 2：如果ch優(yōu)先級(jí)低于或者等于top，那么輸出top，然后將ch放入堆棧。 （4）如果表達(dá)式已經(jīng)讀取完成，而堆棧中還有運(yùn)算符時(shí)，依次由頂端輸出。 如果我們有表達(dá)式(A-B)*C+D-E/F，要翻譯成后綴表達(dá)式，并且把后綴表達(dá)式存儲(chǔ)在一個(gè)名叫output的字符串中，可以用下面的步驟。 （1）讀取'('，壓入堆棧，output為空 （2）讀取A，是運(yùn)算數(shù)，直接輸出到output字符串，output = A （3）讀取'-'，此時(shí)棧里面只有一個(gè)'('，因此將'-'壓入棧，output = A （4）讀取B，是運(yùn)算數(shù)，直接輸出到output字符串，output = AB （5）讀取')'，這時(shí)候依次輸出棧里面的運(yùn)算符'-'，然后就是'('，直接彈出，output = AB- （6）讀取'*'，是運(yùn)算符，由于此時(shí)棧為空，因此直接壓入棧，output = AB- （7）讀取C，是運(yùn)算數(shù)，直接輸出到output字符串，output = AB-C （8）讀取'+'，是運(yùn)算符，它的優(yōu)先級(jí)比'*'低，那么彈出'*'，壓入'+"，output = AB-C* （9）讀取D，是運(yùn)算數(shù)，直接輸出到output字符串，output = AB-C*D （10）讀取'-'，是運(yùn)算符，和'+'的優(yōu)先級(jí)一樣，因此彈出'+'，然后壓入'-'，output = AB-C*D+ （11）讀取E，是運(yùn)算數(shù)，直接輸出到output字符串，output = AB-C*D+E （12）讀取'/'，是運(yùn)算符，比'-'的優(yōu)先級(jí)高，因此壓入棧，output = AB-C*D+E （13）讀取F，是運(yùn)算數(shù)，直接輸出到output字符串，output = AB-C*D+EF （14）原始字符串已經(jīng)讀取完畢，將棧里面剩余的運(yùn)算符依次彈出，output = AB-C*D+EF/- 5 計(jì)算算術(shù)表達(dá)式 當(dāng)有了后綴表達(dá)式以后，運(yùn)算表達(dá)式的值就非常容易了?？梢园凑障旅娴牧鞒虂?lái)計(jì)算。 （1）從左向右掃描表達(dá)式，一個(gè)取出一個(gè)數(shù)據(jù)data （2）如果data是操作數(shù)，就壓入堆棧 （3）如果data是操作符，就從堆棧中彈出此操作符需要用到的數(shù)據(jù)的個(gè)數(shù)，進(jìn)行運(yùn)算，然后把結(jié)果壓入堆棧 （4）如果數(shù)據(jù)處理完畢，堆棧中最后剩余的數(shù)據(jù)就是最終結(jié)果。 比如我們要處理一個(gè)后綴表達(dá)式1234+*+65/-，那么具體的步驟如下。 （1）首先1，2，3，4都是操作數(shù)，將它們都?jí)喝攵褩?br> （2）取得'+'，為運(yùn)算符，彈出數(shù)據(jù)3，4，得到結(jié)果7，然后將7壓入堆棧 （3）取得'*'，為運(yùn)算符，彈出數(shù)據(jù)7，2，得到數(shù)據(jù)14，然后將14壓入堆棧 （4）取得'+'，為運(yùn)算符，彈出數(shù)據(jù)14，1，得到結(jié)果15，然后將15壓入堆棧 （5）6，5都是數(shù)據(jù)，都?jí)喝攵褩?br> （6）取得'/'，為運(yùn)算符，彈出數(shù)據(jù)6，5，得到結(jié)果1.2，然后將1.2壓入堆棧 （7）取得'-'，為運(yùn)算符，彈出數(shù)據(jù)15，1.2，得到數(shù)據(jù)13.8，這就是最后的運(yùn)算結(jié)果 6 示例代碼 /// <summary>
/// 將中綴表達(dá)式翻譯成后綴表達(dá)式 /// 輸入中綴表達(dá)式： A+B*(C+D)-E/F /// 翻譯成后綴表達(dá)式：ABCD+*+EF/- /// 中綴表達(dá)式翻譯成后綴表達(dá)式的方法如下： /// （1）從左向右依次取得數(shù)據(jù)ch /// （2）如果ch是操作數(shù)，直接輸出 /// （3）如果ch是運(yùn)算符（含左右括號(hào)），則： /// a：如果ch = '('，放入堆棧 /// b：如果ch = ')'，依次輸出堆棧中的運(yùn)算符，直到遇到'('為止 /// c：如果ch不是')'或者'('，那么就和堆棧頂點(diǎn)位置的運(yùn)算符top做優(yōu)先級(jí)比較 /// 1：如果ch優(yōu)先級(jí)比top高，那么將ch放入堆棧 /// 2：如果ch優(yōu)先級(jí)低于或者等于top，那么輸出top，然后將ch放入堆棧 /// （4）如果表達(dá)式已經(jīng)讀取完成，而堆棧中還有運(yùn)算符時(shí)，依次由頂端輸出 /* Pseudocode() { n = passing(s, op); //s是表達(dá)式，op是數(shù)據(jù)數(shù)組，n是數(shù)據(jù)的數(shù)量 for(int i=0; i<n; i++) { ch = op(i); if(ch是操作數(shù)) output(ch); else { if(ch == '(') push(ch); else if( ch == ')') pop()而且輸出，直到遇到'('為止; else { if(運(yùn)算符ch較stack[top]優(yōu)先) push(ch); else { pop()且輸出; push(ch); } } } } */ /// </summary> public class PosfixParser { private static string expression = "1+4/(1+1)+2*(3+4)-6/3+5/(1/2+2/1)"; private static Stack myStack = new Stack(); private static StringBuilder posfixExpression = new StringBuilder(); public static void Main() { Console.WriteLine("This Midfix expression is: {0}", expression); Console.WriteLine("The Posfix expression is: {0}", Parse()); Console.WriteLine("The result is {0}", Calculate()); Console.Read(); } //將中綴表達(dá)式解析成后綴表達(dá)式 public static string Parse() { int i, j = 0; char ch, ch1; char[] A = expression.ToCharArray(); //將字符串轉(zhuǎn)成字符數(shù)組，要注意的是，不能有大于10的數(shù)存在 char[] B = new char[A.Length]; //最后生成的后綴表達(dá)式會(huì)小于這個(gè)長(zhǎng)度，因?yàn)橛欣ㄌ?hào) int length = A.Length; for(i=0; i<length; i++) { ch = A[i]; if( IsOperand( ch ) ) //如果是操作數(shù)，直接放入B中 { B[j++] = ch; } else { if( ch == '(' ) //如果是'('，將它放入堆棧中 myStack.Push(ch); else if( ch == ')') //如果是')' { while( !IsEmpty(myStack) ) //不停地彈出堆棧中的內(nèi)容，直到遇到'(' { ch = (char)myStack.Pop(); if( ch == '(' ) break; else B[j++] = ch; //將堆棧中彈出的內(nèi)容放入B中 } } else //既不是'('，也不是')'，是其它操作符，比如+, -, *, /之類的 { if( !IsEmpty( myStack ) ) { do { ch1 = (char)myStack.Pop();//彈出棧頂元素 if(Priority(ch) > Priority(ch1)) //如果棧頂元素的優(yōu)先級(jí)小于讀取到的操作符 { myStack.Push(ch1);//將棧頂元素放回堆棧 myStack.Push(ch);//將讀取到的操作符放回堆棧 break; } else//如果棧頂元素的優(yōu)先級(jí)比較高或者兩者相等時(shí) { B[j++] = ch1; //將棧頂元素彈出，放入B中 if( IsEmpty(myStack) ) { myStack.Push(ch); //將讀取到的操作符壓入堆棧中 break; } } } while( !IsEmpty(myStack)); } else //如果堆棧為空，就把操作符放入堆棧中 { myStack.Push(ch); } } } } while( !IsEmpty(myStack ) ) B[j++] = (char)myStack.Pop();//將堆棧中剩下的操作符輸出到B中 for(i=0; i<B.Length; i++) if( B[i] != '\0' ) //去除多余的空字符 posfixExpression.Append(B[i]); return posfixExpression.ToString(); } //計(jì)算后綴表達(dá)式的值 public static double Calculate() { int i; double no1, no2, ret; char ch; char[] A = posfixExpression.ToString().ToCharArray(); myStack.Clear(); for(i=0; i<A.Length; i++) { ch = A[i]; if(IsOperand(ch))//如果是操作數(shù)，直接壓入棧 { myStack.Push((double)(ch-48)); } else //如果是操作符，就彈出兩個(gè)數(shù)字來(lái)進(jìn)行運(yùn)算 { no1 = (double) myStack.Pop(); no2 = (double) myStack.Pop(); ret = GetValue(ch, no1, no2); myStack.Push(ret);//將結(jié)果壓入棧 } } return (double)myStack.Pop();//彈出最后的運(yùn)算結(jié)果 } //對(duì)兩個(gè)值利用運(yùn)算符計(jì)算結(jié)果 private static double GetValue(char op, double ch1, double ch2) { switch( op ) { case '+': return ch2 + ch1; case '-': return ch2 - ch1; case '*': return ch2 * ch1; case '/': return ch2 / ch1; default: return 0; } } //判斷堆棧是否為空 private static bool IsEmpty(Stack st) { return st.Count == 0 ? true: false; } //判斷是否是操作數(shù) private static bool IsOperand( char ch ) { char[] operators = { '+', '-', '*', '/', '(', ')' }; for(int i=0; i<operators.Length; i++) if( ch == operators[i] ) return false; return true; } //返回運(yùn)算符的優(yōu)先級(jí) private static int Priority( char ch ) { int priority; switch( ch ) { case '+' : priority = 1; break; case '-' : priority = 1; break; case '*' : priority = 2; break; case '/' : priority = 2; break; default : priority = 0; break; } return priority; } } 利用上述程序可以求解只包含+，-，*，/，()和0－9之間的數(shù)字的表達(dá)式的值。這只是一個(gè)相當(dāng)初級(jí)的程序，還有很多工作沒(méi)有完成，但是只要我們弄清楚了其中的過(guò)程和步驟，剩下的工作就不再是那么困難了。 |
|
|
