import java.util.Stack;
import java.util.Scanner;

public class Evaluate {
	public static void main(String[] args) {
		Stack<String> ops=new Stack<String>();
		Stack<Double> vals=new Stack<Double>();
		Scanner cin=new  Scanner(System.in);
		//输入的表达式不能省略括号
		System.out.println("Input a cal string end with ‘$‘:");
		while(cin.hasNext()){
			String s=cin.next();
			if(s.equals("$")) break;
			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 op=ops.pop();
				double v=vals.pop();
				if(op.equals("+")) v=vals.pop()+v;
				else if(op.equals("-")) v=vals.pop()-v;
				else if(op.equals("*")) v=vals.pop()*v;
				else if(op.equals("/")) v=vals.pop()/v;
				else if(op.equals("sqrt")) v=Math.sqrt(v);
				//将计算后的结果入栈
				vals.push(v);
			}
			//如果是数字，则作为double值入栈
			else {
				vals.push(Double.parseDouble(s));
			}
		}
		//打印结果
		System.out.println(vals.pop());
	}
}

//output example
Input a cal string end with ‘$‘:
( 1 + ( 1 + sqrt ( 9 ) ) + ( 4 * 3 ) ) $
16.0