中缀表达式转后缀表达式
转换过程如下:
1、运算数:直接输出;
2、左括号:压入堆栈;
3、右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出);
4、运算符:若优先级大于栈顶运算符时,则把它压栈;若优先级小于等于栈顶运算符时,将栈顶运算符弹出并输出;再比较新的栈顶运算符,直到该运算符大于栈顶运算符优先级为止,然后将该运算符压栈;
5、若各对象处理完毕,则把堆栈中存留的运算符一并输出
(以上来自中国大学慕课浙江大学数据结构)
后缀表达式求值看下篇:http://lovedm.club/?id=130
C#代码实现如下:
using System; using System.Collections.Generic; namespace 中缀表达式转后缀表达式 { class Program { static void Main(string[] args) { //string[] expression = { "(", "4", "+", "(", "13", "/", "5", ")", ")" }; string[] expression = { "(", "(", "10", "*", "(", "6", "/", "(", "(", "9", "+", "3", ")", "*", "-11", ")", ")", ")", "+", "17", ")", "+", "5" }; foreach (var item in ConvertExpression(expression)) { Console.Write(item + " "); } } /// <summary> /// 优先级比较 /// 只比较“+”,“-”,“*”,“/”和“(”之间的优先级 /// 且优先级相同时返回false /// </summary> /// <param name="left">左边的运算符</param> /// <param name="right">右边的运算符</param> /// <returns>左边的优先级大于右边返回true,小于或等于时返回false</returns> public static bool Priority(string left, string right) { if (left == "+" || left == "-") { if (right == "*" || right == "/" || right == "+" || right == "-") { return false; } } if (left == "*" || left == "/") { if (right == "*" || right == "/") { return false; } } return true; } /// <summary> /// 中缀表达式转后缀表达式 /// </summary> /// <param name="s">以字符串数组形式输入的中缀表达式</param> /// <returns>返回后缀表达式的集合</returns> public static List<string> ConvertExpression(string[] s) { int length = s.Length; Stack<string> stack = new Stack<string>(); List<string> answer = new List<string>(); //遍历所有元素 for (int i = 0; i < length; i++) { //遇到运算数直接添加到结果 int num; if (int.TryParse(s[i].ToString(), out num)) { answer.Add(s[i]); } //遇到左括号直接压入栈 if (s[i] == "(") { stack.Push("("); } //遇到右括号依次弹出栈顶元素到结果直至遇到左括号 if (s[i] == ")") { string element = stack.Pop(); while (element != "(") { answer.Add(element); element = stack.Pop(); } } //如果是运算符则比较运算符的优先级: //1、若优先级大于栈顶运算符则压入栈 //2、若优先级小于等于栈顶的运算符,则将栈顶运算符弹出并添加到结果, //再比较栈顶的新运算符,直至该运算符大于栈顶运算符优先级为止, //然后将该运算符压栈 if (s[i] == "+" || s[i] == "-" || s[i] == "*" || s[i] == "/") { //栈内元素为0的话,入栈即可 if (stack.Count == 0) { stack.Push(s[i]); } else //否则按照上面的算法 { string temp = stack.Peek(); if (Priority(s[i], temp)) { stack.Push(s[i]); } else { answer.Add(stack.Pop()); while (!Priority(s[i], stack.Peek())) { answer.Add(stack.Pop()); } stack.Push(s[i]); } } } } //若各对象处理完毕,则把堆栈中存留的运算符一并加入到结果 while (stack.Count != 0) { answer.Add(stack.Pop()); } return answer; } } }
输出结果如下: