algs1.3.10 简单衍生 中缀转前缀

InfixToPrefix.java

package life.yanfeng.study.algorithm;

import edu.princeton.cs.algs4.StdOut;

// 1.3.10 衍生 中缀转前缀
public class InfixToPrefix {
    /// 自动补全 左括号 . 反向推导表达式的原始形式.
    /// 核心思路, 也即: 双栈表达式的精髓在于: 使用同一个栈, 同时存储 操作数 和 中间运算结果.
    static String transform(String exp) {
        Stack<String> ops = new Stack<>();
        Stack<String> vals = new Stack<>();

        for (String s : exp.split(" ")) {
            // 读取字符串, 如果是运算符则压入栈.
            if (s.equals("(")) {
                continue;
            } else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                ops.push(s);
            } else if(s.equals(")")) {
                // 如果字符维 ")", 则弹出运算符和操作数, 计算结果,并将结果压入栈.
                String op = ops.pop();
                String v1 = vals.pop();
                String v2 = vals.pop();

                // 简化实现.假设都是 三元操作符.
                String v = String.format("( %s %s %s )", op, v2, v1);
                vals.push(v);
            } else { // 如果既不是运算符,也不是括号, 则将它作为 值压入栈.
                vals.push(s);
            }
        }

        return vals.pop();
    }

    public static void main(String[] args) {
        String exp = "( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )";
        String fullExp = transform(exp);

        // output: ( ( 1 2 + ) ( ( 3 4 - ) ( 5 6 - ) * ) * )
        StdOut.println(fullExp);
    }
}