逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)。
一个表达式E的后缀形式可以如下定义:
(1)如果E是一个变量或常量,则E的后缀式是E本身。
(2)如果E是E1 op E2形式的表达式,这里op是任何二元操作符,则E的后缀式为E1’E2’ op,这里E1’和E2’分别为E1和E2的后缀式。
(3)如果E是(E1)形式的表达式,则E1的后缀式就是E的后缀式。
如:我们平时写a+b,这是中缀表达式,写成后缀表达式就是:ab+
c-(a+b)/e的后缀表达式为:
c-(a+b)/e
c)((a+b)/e)-)(ab+e/)-
→ab+c
ab+e/-将一个普通的中序表达式转换为逆波兰表达式的一般算法是:
首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为输入逆波兰式的栈S2(空栈),S1栈可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束。可指定其他字符,不一定非#不可。从中缀式的左端开始取字符,逐序进行如下步骤:
完成以上步骤,S2栈便为逆波兰式输出结果。不过S2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了!
新建一个栈,如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。
import java.util.*; /** * 逆波兰式生成 */ public class RPN { public static void main(String[] args) { RPN("(${var1}+${var2})*1000/${var3} "); RPN("(a+b)*c-(a+b)/e "); System.out.println(compute(RPN("100/10"))); } static Set<String> operator = new HashSet<String>() {{ add("+"); add("-"); add("*"); add("/"); }}; static Map<String, Integer> operatorLevelMap = new HashMap<String, Integer>() {{ put("+", 0); put("-", 0); put("*", 1); put("/", 1); }}; static Set<String> brackets = new HashSet<String>() {{ add("("); add(")"); }}; static String bracketLeft = "("; static String bracketRight = ")"; static String opType = "$"; static String opStart = "{"; static String opStop = "}"; static String space = " "; public static Double compute(LinkedList<String> s1) { LinkedList<Double> stack = new LinkedList<Double>(); while (s1.size() != 0) { String tmp = s1.pop(); if (operator.contains(tmp)) { Double d2 = stack.pop(); Double d1 = stack.pop(); Double r = doCompute(d1, d2, tmp); stack.push(r); } else { stack.push(Double.valueOf(tmp)); } } return stack.pop(); } private static Double doCompute(Double d1, Double d2, String operator) { switch (operator) { case "+": return d1 + d2; case "-": return d1 - d2; case "*": return d1 * d2; case "/": return d1 / d2; default: throw new RuntimeException("操作符异常" + operator); } } /** * 生成逆波兰式 */ public static LinkedList<String> RPN(String str) { StringHolder holder = new StringHolder(str); // 临时存储运算符 LinkedList<String> s1 = new LinkedList<String>(); // 输入逆波兰式 LinkedList<String> s2 = new LinkedList<String>(); while (!holder.finished()) { // 5. 重复以下的1~4步,直至处理完所有的输入字符 String tmp = holder.next(); while (space.equals(tmp)) { tmp = holder.next(); } if (tmp == null) { break; } if (!operator.contains(tmp) && !brackets.contains(tmp)) { // 1. 若取出的字符是操作数,则分析出完整的运算数,该操作数直接送入S2栈 s2.push(getOp(holder)); } else if (operator.contains(tmp)) { // 2. 若取出的字符是运算符,则将该运算符与S1栈栈顶元素比较 Integer operatorLevel = operatorLevelMap.get(tmp); String s1Top = s1.peekFirst(); Integer s1TopLevel = operatorLevelMap.get(s1Top); if (s1.size() == 0 || bracketLeft.equals(s1Top) || (operatorLevel - s1TopLevel) > 0) { // 2.1 如果该运算符优先级(不包括括号运算符)大于S1栈栈顶运算符优先级,则将该运算符进S1栈 s1.push(tmp); } else { // 2.2.1 否则,将S1栈的栈顶运算符弹出,送入S2栈中,直至S1栈栈顶运算符低于(不包括等于)该运算符优先级 while (s1.size() != 0 && !bracketLeft.equals(s1Top) && (operatorLevel - s1TopLevel) <= 0) { s2.push(s1.pop()); s1Top = s1.peekFirst(); s1TopLevel = operatorLevelMap.get(s1Top); } // 2.2.2 最后将该运算符送入S1栈。 s1.push(tmp); } } else if (bracketLeft.equals(tmp)) { // 3. 若取出的字符是“(”,则直接送入S1栈顶。 s1.push(tmp); } else if (bracketRight.equals(tmp)) { // 4. 若取出的字符是“)”,则将距离S1栈栈顶最近的“(”之间的运算符,逐个出栈,依次送入S2栈,此时抛弃“(”。 while (s1.size() != 0 && !bracketLeft.equals(s1.peekFirst())) { s2.push(s1.pop()); } } } // 6. 将S1栈内所有运算符(不包括“#”),逐个出栈,依次送入S2栈。 while (s1.size() != 0) { if (s1.peekFirst().equals(bracketLeft)) { s1.pop(); } else { s2.push(s1.pop()); } } Collections.reverse(s2); System.out.println(String.join(",", s2)); return s2; } /** * 获取操作数 */ public static String getOp(StringHolder holder) { if (opType.equals(holder.current())) { // 变量 除非遇到结束符,否则不结束 StringBuilder builder = new StringBuilder(opType); // 如果字符未结束,并且下一个字符不是变量结束符。就添加下一个字符 while (!holder.finished() && !opStop.equals(holder.next())) { builder.append(holder.current()); } if (!opStop.equals(holder.current())) { throw new RuntimeException(String.format("变量%s有误", builder.toString())); } builder.append(opStop); return builder.toString(); } else { // 常量 StringBuilder builder = new StringBuilder(holder.current()); while (!holder.finished()) { if (!constantEnd(holder.next())) { builder.append(holder.current()); } else { holder.back(); break; } } return builder.toString(); } } public static String constant = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890._"; public static boolean constantEnd(String tmp) { if (space.equals(tmp) || operator.contains(tmp) || brackets.contains(tmp)) { // 空格 操作符 括号 return true; } if (!constant.contains(tmp)) { // 常规字符 return true; } return false; } public static class StringHolder { private String str; private int pos; private String tmp; public StringHolder(String str) { this.str = str; this.pos = -1; } public String next() { if (pos + 1 == str.length()) { this.tmp = null; } else { pos++; this.tmp = String.valueOf(str.charAt(pos)); } return this.tmp; } public void back() { this.pos--; this.tmp = String.valueOf(str.charAt(pos)); } public String current() { return tmp; } public boolean finished() { return pos + 1 == str.length(); } } }