Ex1_3_9 补全缺少左括号的中缀表达式

Ex1_3_9 补全缺少左括号的中缀表达式

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Ex1_3_9 {
    public static void main(String[] args){
        Stack<String> vals = new Stack<>();
        Stack<String> ops = new Stack<>();
        while (!StdIn.isEmpty()){
            String s = StdIn.readString();
            if(s.equals("+")) ops.push(s);
            else if(s.equals("-")) ops.push(s);
            else if(s.equals("*")) ops.push(s);
            else if(s.equals("/")) ops.push(s);
            else if(s.equals("sqrt")) ops.push(s);
            else if(s.equals(")")){
                String op= ops.pop();
                String val = vals.pop();
                if(op.equals("sqrt")){//需满足sqrt中为两个值的运算
                    String exp = String.format("( %s %s )",op,val);
                    vals.push(exp);
                }else {
                    String exp = String.format("( %s %s %s )", vals.pop(), op, val);
                    vals.push(exp);
                }
            }
            else{
                vals.push(s);
            }
        }
        StdOut.println(vals.pop());
    }
}
*/1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )补全后
( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )
sqrt 3 + 5 ) )补全后
( sqrt ( 3 + 5 ) )
/*

要点:

1. 使用堆栈,用String.format()前各弹出一个符号和数值