逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)。

定义

一个表达式E的后缀形式可以如下定义:<br/>
(1)如果E是一个变量或常量,则E的后缀式是E本身。<br/>
(2)如果E是E1 op E2形式的表达式,这里op是任何二元操作符,则E的后缀式为E1'E2' op,这里E1'和E2'分别为E1和E2的后缀式。<br/>
(3)如果E是(E1)形式的表达式,则E1的后缀式就是E的后缀式。<br/>
如:我们平时写a+b,这是中缀表达式,写成后缀表达式就是:ab+<br/>
(a+b)*c-(a+b)/e的后缀表达式为:<br/>
(a+b)*c-(a+b)/e<br/>
→((a+b)*c)((a+b)/e)-<br/>
→((a+b)c*)((a+b)e/)-<br/>
→(ab+c*)(ab+e/)-<br/>
→ab+c*ab+e/-<br/>

算法实现

将一个普通的中序表达式转换为逆波兰表达式的一般算法是:

首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为输入逆波兰式的栈S2(空栈),S1栈可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束。可指定其他字符,不一定非#不可。从中缀式的左端开始取字符,逐序进行如下步骤:

  1. 若取出的字符是操作数,则分析出完整的运算数,该操作数直接送入S2栈
  2. 若取出的字符是运算符,则将该运算符与S1栈栈顶元素比较,如果该运算符优先级(不包括括号运算符)大于S1栈栈顶运算符优先级,则将该运算符进S1栈,否则,将S1栈的栈顶运算符弹出,送入S2栈中,直至S1栈栈顶运算符低于(不包括等于)该运算符优先级,最后将该运算符送入S1栈。
  3. 若取出的字符是“(”,则直接送入S1栈顶。
  4. 若取出的字符是“)”,则将距离S1栈栈顶最近的“(”之间的运算符,逐个出栈,依次送入S2栈,此时抛弃“(”。
  5. 重复上面的1~4步,直至处理完所有的输入字符
  6. 若取出的字符是“#”,则将S1栈内所有运算符(不包括“#”),逐个出栈,依次送入S2栈。

完成以上步骤,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();
        }
    }
}

标签: java, 算法, 逆波兰式

添加新评论