//1.3.9

//only support +-*/ sqrt operator

package com.qiusongde;

import edu.princeton.cs.algs4.StdIn;

import edu.princeton.cs.algs4.StdOut;

public class AddLeftParentheses {

    public static void main(String[] args) {

        Stack<String> ops = new Stack<String>();

        Stack<String> vals = new Stack<String>();

        while(!StdIn.isEmpty()) {

            String s = StdIn.readString();

            if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("sqrt")) {

                ops.push(s);

            }

            else if(s.equals(")")) {

                String op = ops.pop();//operator

                String v = vals.pop();//value

                if(op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/")) {

                    String subexpression = "( " + vals.pop() + " " + op  + " " + v + " )";

                    vals.push(subexpression);

                }

                if(op.equals("sqrt")) {

                    String subexpression = op + " ( " + v + " )";

                    vals.push(subexpression);

                }

            }

            else {

                vals.push(s);

            }

        }

        StdOut.println(vals.pop());

    }

}