Ex1_3_10 中序转后序

Ex1_3_10 中序转后序

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Ex1_3_10 {
    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("("));
            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("/")) ops.push(s);
            else if(s.equals("sqrt")) ops.push(s);
            else if(s.equals(")")){
                String val = vals.pop();
                String op = ops.pop();
                if(op.equals("sqrt")){
                    String temp = String.format("%s %s",val,op);
                    vals.push(temp);
                }else{
                    String temp = String.format("%s %s %s",vals.pop(),val,op);
                    vals.push(temp);
                }
            }
            else vals.push(s);
        }
        StdOut.println(vals.pop());
     }
}
//( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )转为1 2 + 3 4 - 5 6 - * *

要点:

1. 使用双栈法的变形
2. 中序表达式一定需要满足两个一组用括号括起