程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> 使用棧Stack對整數數值的運算表達式字符串進行運算C#,

使用棧Stack對整數數值的運算表達式字符串進行運算C#,

編輯:C#入門知識

使用棧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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved