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(" 后缀表达式对应的List："+str); //结果计算 int result =PolandNotation.Calculate(suffixExpression); Console.WriteLine($" {expression}={result}"); } }
