01.06
逆波兰表达式将操作符置于操作数的后面。比如,3+4用逆波兰表示法则是 “3 4 +”。 更复杂的,7+8*2 则是 “7 8 2 * +”。
将算术表达式转换成逆波兰表达式的算法如下:
1. 分配2个栈,栈s1用于临时存储运算符(含一个结束符号);栈s2用于输入逆波兰式,为方便起见,栈s1需先放入一个优先级最低的运算符,在这里假定为’#’;
2. 从算术表达式的左端开始逐个读取字符x,逐序进行如下步骤:
(1)若x是操作数,则分析出完整的运算数(在这里为方便,用字母代替数字),将x直接压入栈s2;
(2)若x是运算符,则分情况讨论:
若x是'(‘,则直接压入栈s1;
若x是’)’,则将距离栈s1栈顶的最近的'(‘之间的运算符,逐个出栈,依次压入栈s2,此时抛弃'(‘;
若x是除'(‘和’)’外的运算符,则再分如下情况讨论:
若当前栈s1的栈顶元素为'(‘,则将x直接压入栈s1;
若当前栈s1的栈顶元素不为'(‘,则将x与栈s1的栈顶元素比较,若x的优先级大于栈s1栈顶运算符优先级,则将x直接压入栈s1。否者,将栈s1的栈顶运算符弹出,压入栈s2中,直到栈s1的栈顶运算符优先级别低于(不包括等于)x的优先级,或栈s1的栈顶运算符为'(‘或”#”。最后再则将x压入栈s1;
3. 在进行完2后,检查栈s1是否为空,若不为空,则将栈中元素依次弹出并压入栈s2中(不包括’#’);
4. 完成上述步骤后,栈s2便为逆波兰式输出结果。但是栈s2应做一下逆序处理,因为此时表达式的首字符位于栈底。
下面是java实现。
import java.util.ArrayList; import java.util.List; import java.util.Stack; public class ReversePolishNotation { private final static String PLUS = "+"; private final static String MINUS = "-"; private final static String MULTIPLY = "*"; private final static String DIVIDE = "/"; private final static String POINT = "."; private final static String OPSTART = "("; private final static String OPEND = ")"; private final static String NUMBER_SIGN = "#"; private String exp; private List<String> expList = new ArrayList<String>(); private List<String> rpnList = new ArrayList<String>(); public ReversePolishNotation(String exp) { this.exp = exp; } private boolean isDigit(String str) { return str.equals("0") || str.equals("1") || str.equals("2") || str.equals("3") || str.equals("4") || str.equals("5") || str.equals("6") || str.equals("7") || str.equals("8") || str.equals("9"); } /** * 是否是负号 * * @param exp * @param ch * @param index * @return */ private boolean isNegativeSign(String exp, String ch, int index) { if (ch.equals("-")) { if (index == 0) { return true; } else { String previous = exp.substring(index - 1, index); if ((!isDigit(previous)) && (!(previous.equals(OPEND)))) { return true; } else { return false; } } } return false; } private void parse() { int length = exp.length(); String tempStr = ""; for (int i = 0; i < length; i++) { String tempChar = exp.substring(i, i + 1); if (isDigit(tempChar) || tempChar.equals(POINT) || isNegativeSign(exp, tempChar, i)) { tempStr += tempChar; } else { if (!tempStr.equals("")) { expList.add(tempStr); } expList.add(tempChar); tempStr = ""; } } if (!tempStr.equals("")) { expList.add(tempStr); } } private boolean isNumber(String str) { try { Double.parseDouble(str); return true; } catch (NumberFormatException e) { return false; } } /** * 运算符str1 是否比str2优先级高 * * @param str1 * @param str2 * @return */ private boolean prior(String str1, String str2) { if ((str1.equals(MULTIPLY) || str1.equals(DIVIDE)) && (str2.equals(PLUS) || str2.equals(MINUS))) { return true; } else if ((str1.equals(PLUS) || str1.equals(MINUS) || str1.equals(MULTIPLY) || str1.equals(DIVIDE)) && str2.equals(NUMBER_SIGN)) { return true; } return false; } /** * 运算符str1 是否比str2优先级低 * * @param str1 * @param str2 * @return */ private boolean posterior(String str1, String str2) { if ((str1.equals(PLUS) || str1.equals(MINUS)) && (str2.equals(MULTIPLY) || str2.equals(DIVIDE))) { return true; } else if (str1.equals(NUMBER_SIGN) && (str2.equals(PLUS) || str2.equals(MINUS) || str2.equals(MULTIPLY) || str2.equals(DIVIDE))) { return true; } return false; } private void generateRPN() { Stack<String> s1 = new Stack<String>(); s1.push(NUMBER_SIGN); Stack<String> s2 = new Stack<String>(); for (int i = 0; i < expList.size(); i++) { String item = expList.get(i); if (isNumber(item)) { s2.push(item); } else if (item.equals(OPSTART)) { s1.push(item); } else if (item.equals(OPEND)) { String c; do { c = s1.pop(); if (!c.equals(OPSTART)) { s2.push(c); } } while (!c.equals(OPSTART)); } else { String top = s1.peek(); if (top.equals("(")) { s1.push(item); } else { if (prior(item, top)) { s1.push(item); } else { String c; do { c = s1.pop(); s2.push(c); if (posterior(s1.peek(), item) || s1.peek().equals("(") || s1.peek().equals(NUMBER_SIGN)) { break; } } while (true); s1.push(item); } } } } while (!s1.isEmpty()) { String c = s1.pop(); if (!c.equals(NUMBER_SIGN)) { s2.push(c); } } rpnList = new ArrayList<String>(); rpnList.addAll(s2); } public List<String> getRPN() { parse(); generateRPN(); return rpnList; } /** * @param args */ public static void main(String[] args) { String exp = "7+8*2"; ReversePolishNotation rpn = new ReversePolishNotation(exp); List<String> rpnExp = rpn.getRPN(); System.out.println("算术表达式:" + exp); System.out.println("逆波兰表达式:" + rpnExp); exp = "(30-4*5)*(3+5)-5"; rpn = new ReversePolishNotation(exp); rpnExp = rpn.getRPN(); System.out.println("算术表达式:" + exp); System.out.println("逆波兰表达式:" + rpnExp); exp = "(8-4)*(88/2/11)"; rpn = new ReversePolishNotation(exp); rpnExp = rpn.getRPN(); System.out.println("算术表达式:" + exp); System.out.println("逆波兰表达式:" + rpnExp); } }
控制台输出如下:
算术表达式:7+8*2
逆波兰表达式:[7, 8, 2, *, +]
算术表达式:(30-4*5)*(3+5)-5
逆波兰表达式:[30, 4, 5, *, -, 3, 5, +, *, 5, -]
算术表达式:(8-4)*(88/2/11)
逆波兰表达式:[8, 4, -, 88, 2, /, 11, /, *]