import java.util.Stack;
public class Homework
{
  public static int eval(ExpressionTree root)
  {
    if(!root.isOper())
      return Integer.valueOf(""+root.getValue());
    if((""+root.getValue()).equals("*"))
      return eval(root.getLeft()) * eval(root.getRight());
    if((""+root.getValue()).equals("+"))
      return eval(root.getLeft()) + eval(root.getRight());
    return 0;
  }
  public static String toInfixNotation(ExpressionTree root)
  {
    if(!root.isOper())
    {
      return ""+root.getValue();
    }
    return "( " + toInfixNotation(root.getLeft()) + " " + root.getValue() + " " + toInfixNotation(root.getRight()) + ")";
  }
  public static int eval(String[] tokens)
  {
    Stack<Integer> stk = new Stack<Integer>();
    for(String r: tokens)
    {
      if(Character.isDigit(r.charAt(0)))
      {
        stk.push(Integer.valueOf(r));
      }
      if(r.equals("+"))
        stk.push(stk.pop() + stk.pop());
      if(r.equals("*"))
        stk.push(stk.pop() * stk.pop());
    }
    return stk.pop();
  }
  public static void main()
  {
    ExpressionTree n9 = new ExpressionTree("3");
    ExpressionTree n8 = new ExpressionTree("2");
    ExpressionTree n7 = new ExpressionTree("+",n8,n9);
    ExpressionTree n6 = new ExpressionTree("4");
    ExpressionTree n5 = new ExpressionTree("6");
    ExpressionTree n4 = new ExpressionTree("5");
    ExpressionTree n3 = new ExpressionTree("*",n6,n7);
    ExpressionTree n2 = new ExpressionTree("+",n4,n5);
    ExpressionTree n1 = new ExpressionTree("*",n2,n3);
    System.out.println(eval(n1));
    System.out.println(toInfixNotation(n1));
    
    String[] tkns = {"3","2","+","4","6","5","*","+","*"};
    System.out.println(eval(tkns));
  }
    
  
 
}