C#數據結構與演算法系列（十一）：中綴表達式轉後綴表達式
1.具體步驟
1）初始化兩個棧：運算符棧s1和儲存中間結果的棧s2；
2）從左至右掃描中綴表達式；
3）遇到操作數時，將其壓s2；
4）遇到運算符時，比較其與s1棧頂運算符的優先順序：
（1）如果s1為空，或棧頂運算符為左括弧「(」，則直接將此運算符入棧；
（2）否則，若優先順序比棧頂運算符的高，也將運算符壓入s1；
（3）否則，將s1棧頂的運算符彈出並壓入到s2中，再次轉到(4-1)與s1中新的棧頂運算符相比較；
5）遇到括弧時：
（1）如果是左括弧「(」，則直接壓入s1
（2）如果是右括弧「)」，則依次彈出s1棧頂的運算符，並壓入s2，直到遇到左括弧為止，此時將這一對括弧丟棄
6）重複步驟2至5，直到表達式的最右邊
7）將s1中剩餘的運算符依次彈出並壓入s2
8）依次彈出s2中的元素並輸出，結果的逆序即為中綴表達式對應的後綴表達式
2.思路分析
3.程式碼實現
/// <summary> /// 字元串轉中綴表達式的List /// </summary> /// <param name="expression"></param> /// <returns></returns> public static List<string> ToInfixExpression(string expression) { List<string> list = new List<string>(); int index = 0; string str = ""; do { //48-57ASCII碼代表的是0-9 如果不是0-9直接入鏈表 if (expression[index] < 48 || expression[index] > 57)//ascii編碼 { list.Add("" + expression[index]); index++; } else { str = ""; //多位數判斷 while (index < expression.Length && expression[index] >= 48 && expression[index] <= 57) { str += expression[index]; index++; } list.Add(str); } } while (index < expression.Length); return list; }
/// <summary> /// 中綴轉後綴 /// </summary> /// <param name="expression"></param> /// <returns></returns> public static List<string> ParseSuffixExpression(List<string> expression) { //存儲中間結果 List<string> list = new List<string>(); //符號棧 Stack<string> stack = new Stack<string>(); foreach (var item in expression) { //多位數判斷 如果是數字直接加入list if (Regex.IsMatch(item, "\\d+")) { list.Add(item); } //如果是左括弧，直接入符號棧 else if (item.Equals("(")) { stack.Push(item); } //如果是右括弧 else if (item.Equals(")")) { //依次彈出stack棧頂的運算符，並存入list,直到遇到左括弧為止 while (!stack.Peek().Equals("(")) { list.Add(stack.Pop()); } //將(也出棧 stack.Pop(); } //如果是*/+- else { //循環判斷item的優先順序小於或者等於stack棧頂運算符，將stack棧頂的運算符出棧並加入到list中 while (stack.Count != 0 && Operation.GetValue(stack.Peek()) >= Operation.GetValue(item)) { list.Add(stack.Pop()); } //將item入棧 stack.Push(item); } } //將stack剩餘的運算符依次入list while (stack.Count!=0) { list.Add(stack.Pop()); } return list; }
public class Operation { private static int ADD = 1; private static int SUB = 1; private static int MUL = 2; private static int DIV = 2; public static int GetValue(string operation) { int result = 0; switch (operation) { case "+": result = ADD; break; case "-": result = SUB; break; case "*": result = MUL; break; case "/": result = DIV; break; default: // Console.WriteLine("不存在該運算符"); break; } return result; } }
/// <summary> /// 計算 /// </summary> /// <param name="list"></param> /// <returns></returns> public static int Calculate(List<string> list) { //創建棧 Stack<string> stack = new Stack<string>(); //循環遍歷 list.ForEach(item => { //正則表達式判斷是否是數字，匹配的是多位數 if (Regex.IsMatch(item,"\\d+")) { //如果是數字直接入棧 stack.Push(item); } //如果是操作符 else { //出棧兩個數字，並運算，再入棧 int num1 =int.Parse(stack.Pop()); int num2 = int.Parse(stack.Pop()); int result = 0; if(item.Equals("+")) { result = num2 + num1; } else if(item.Equals("*")) { result = num2 * num1; } else if(item.Equals("/")) { result = num2 / num1; } else if (item.Equals("-")) { result = num2 - num1; } else { throw new Exception("無法識別符號"); } stack.Push(""+result); } }); //最後把stack中數據返回 return int.Parse(stack.Pop()); }
public class ReversePolandTransformation { public static void Test() { string expression = "1+((2+3)*4)-5"; //將字元串轉換成List List<string> infixExpression = ToInfixExpression(expression); string str = ""; infixExpression.ForEach(item => { str = str + item + ","; }); Console.WriteLine("中綴表達式對應的List:"+str); str = ""; //將中綴表達式轉換成後綴表達式 List<string> suffixExpression = ParseSuffixExpression(infixExpression); suffixExpression.ForEach(item => { str = str + item + ","; }); Console.WriteLine("\n後綴表達式對應的List："+str); //結果計算 int result =PolandNotation.Calculate(suffixExpression); Console.WriteLine($"\n{expression}={result}"); } }
