首页 > 代码库 > 逆波兰式篇（后缀表达式）
逆波兰式篇（后缀表达式）
一、逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面。也称为后缀表达式。
二、一般算法
将一个普通的中序表达式转换为逆波兰表达式的一般算法是：
- 首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。
- 读入一个中缀表达式，为了方便起见，可在其最右端追加一个最低优先级运算符（如：#号）。（这样做的目的是，最后读入#号运算符时将运算符栈中所有运算符都输 出）。
- 从左至右扫描该中缀表达式，如果当前字符是数字，则分析到该数字串的结束，并将该数字串直接输出。
- 如果不是数字，该字符则是运算符，此时需比较该运算符与运算符栈顶运算符的优先关系：
- （1）、若该运算符优先级高于栈顶运算符优先级别（或栈为空），则直接将该运算符压入运算符栈中；
- （2）、若该运算符优先级小于或等于此运算符栈顶的运算符，则弹出栈顶运算符并输出，重复比较、输出，直到栈为空或该运算符优先级高于栈顶运算符，然后将该运算 符入栈。
- 重复上述操作(3)-(4)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，输出结果便是中缀表达式转化为逆波兰表示的简单算术表达式。
三、举例说明
例如中缀表达式：9+(3-1) X 3+10+2，其实是我们人类所理解的四则表达运算式，现在我们将其转为机器方便识别的后缀表达式。
四、算法实现
namespace Eduii.Practice.StackDemo{ /* * 词汇： * postfix expression 后缀表达式 * infix expression 中缀表达式 * prefix expression 前缀表达式 * */ /* *分析： *目前四则运算符包括:(、）、+、-、*、/、% * 优先级： * 1、* 、/、% * 2、+ 、- * 3、( * 4、） * */ /* *拓展： * 1、字符串包含其他字符的判断 * 2、四则运算非个位时 * 3、包含小数点 * 4、包含正负号 * 5、...... */ /* *参考文档 * http://www.cnblogs.com/mygmh/archive/2012/10/06/2713362.html * http://www.nowamagic.net/librarys/veda/detail/2307 * http://www.cnblogs.com/stay-foolish/archive/2012/04/25/2470590.html */ /// <summary> /// 逆波兰式的算法实现 /// </summary> public class RPExpression { /// <summary> /// 使用字符串存储 /// </summary> /// <param name="infixExpression"></param> /// <returns></returns> /* *从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后 *缀表达式的一部分；若是符号，若为‘(’,直接压入操作栈， *若为其他字符则判断其与栈顶符号的优先级，是右括号或优先级低 *于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出， 并将当前符号进栈，一直 *到最终输出后缀表达式为止。 * */ public string Convert2PostfixExpWithString(string infixExpression) { //后缀表达式 string postfixExp = string.Empty; //先处理空格 if (string.IsNullOrWhiteSpace(infixExpression)) return postfixExp; //去除空格 infixExpression = infixExpression.Trim(); //操作栈 Stack<char> operatorStack = new Stack<char>(); //四则表达式长度 int length = infixExpression.Length; //临时存储字符 char temp; //数字 string digital = string.Empty; for (int i = 0; i < length; i++) { temp = infixExpression[i]; bool isOperator = IsOperator(temp); if (isOperator) { if (!string.IsNullOrWhiteSpace(digital)) { postfixExp += string.Format("{0},", digital); digital = string.Empty; } if (temp == ‘(‘) operatorStack.Push(temp); //判断是否为‘(‘ else if (temp == ‘)‘) { //当为‘)’时，直接取出栈顶的元素，直到第一个‘(‘为止 char topElement = operatorStack.Pop(); //返回栈顶元素当不将其移除 while (topElement != ‘(‘) { postfixExp += string.Format("{0},", topElement); if (operatorStack.Count == 0) break; topElement = operatorStack.Pop(); } } else { //栈为空时直接插入当前运算符 if (operatorStack.Count == 0) operatorStack.Push(temp); //栈中存在操作符时要判断优先级 else { char topElement = operatorStack.Peek(); while (topElement != ‘#‘) { if (ComparePriority(temp, topElement) > 0) { operatorStack.Push(temp); topElement = ‘#‘; } else { //当前栈顶出栈 postfixExp += string.Format("{0},", topElement); operatorStack.Pop(); if (operatorStack.Count != 0) topElement = operatorStack.Peek(); else { operatorStack.Push(temp); topElement = ‘#‘; } } } } } } else { //数字拼接 digital += temp; //直接输出数字 if (i == length - 1) { postfixExp += string.Format("{0},", digital); } } } //输出所有的操作 while (operatorStack.Count > 0) { postfixExp += string.Format("{0},", operatorStack.Pop()); } return postfixExp; } //比较优先级 private int ComparePriority(char ch1, char ch2) { int ch1Pri = GetPriority(ch1); int ch2Pri = GetPriority(ch2); return ch1Pri - ch2Pri; } //获得字符优先级 private int GetPriority(char ch) { switch (ch) { case ‘(‘: return -1; case ‘+‘: case ‘-‘: return 0; case ‘*‘: case ‘/‘: case ‘%‘: return 1; default: throw new Exception("未定义操作符."); } } // 判断字符是否为操作符 private bool IsOperator(char ch) { if (ch == ‘+‘ || ch == ‘-‘ || ch == ‘*‘ || ch == ‘/‘ || ch == ‘%‘ || ch == ‘(‘ || ch == ‘)‘) return true; return false; } /// <summary> /// 计算后缀表达式值 /// </summary> /// <param name="expression"></param> /// <returns></returns> /* *从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符 *号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈， 一直到最终获得结果。 */ public decimal CalculatePostfixExp(string expression) { if (string.IsNullOrWhiteSpace(expression)) return 0; //清除空格 expression = expression.Trim(); //数据 decimal digigtal = 0; //取得后缀表达式中的字符 int i = 0; char topElement = expression[i]; Stack<decimal> dataStack = new Stack<decimal>(); while (topElement != ‘#‘) { if (topElement != ‘,‘) { if (IsOperator(topElement)) { //取出栈顶元素进行运算 decimal num1 = dataStack.Pop(); decimal num2 = dataStack.Pop(); decimal result = Calculate(num2, num1, topElement); dataStack.Push(result); } else { int singleDigit = topElement - 48; if (digigtal != 0) digigtal = digigtal * 10 + singleDigit; else digigtal = singleDigit; } } else { if (digigtal != 0) { dataStack.Push(digigtal); digigtal = 0; } } if (i == expression.Length - 1) break; i++; topElement = expression[i]; } return dataStack.Pop(); } //两数相加 private decimal Calculate(decimal num1, decimal num2, char ope) { switch (ope) { case ‘+‘: return num1 + num2; case ‘-‘: return num1 - num2; case ‘*‘: return num1 * num2; case ‘/‘: return num1 / num2; default: throw new ApplicationException("未定义的数据类型."); } } }}
逆波兰式篇（后缀表达式）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。