/* ArithExp.java */
/** 使い型：
 * java -cp . ArithExp [デバッグレベル] [ファイル名]
 * 
 * 第1引数が数値なら、それはデバッグレベルと解釈される。
 *  0以下 -- デバッグ出力なし
 *  1     -- レクサーのデバッグ出力あり
 *  2     -- パーザーのデバッグ出力あり
 *  3以上 -- レクサーとパーザーのデバッグ出力あり
 * 
 * ファイル名が指定されないと、標準入力を使う。
 *
 */

import java.io.*;

/* === トークン === */
enum TokenKind {
  NUMBER, // [1-9][0-9]*
  PLUS,   // '+'
  MINUS,  // '-'
  STAR,   // '*'
  LPAR,   // '(' -- left parenthesis
  RPAR,   // ')' -- right parenthesis
  ILLEGAL,
  EOF
}

class Token {
  public final TokenKind kind;
  public final String data;
  public Token(TokenKind kind, String data) {
    this.kind = kind;
    this.data = data;
  }
  public Token(TokenKind kind) {
    this(kind, null);
  }

  public String toString() {
    return "[" + kind + (data == null ? "" : ":" + data) + "]";
  }
}

/* === レクサー === */
class Lexer {
  public boolean debug = false;

  private PushbackReader input;
  public Lexer(PushbackReader input) {
    this.input = input;
  }

  private Token putback = null; // 戻せるのはトークン1個

  public Token nextToken() throws IOException {
    Token tok;
    if (putback != null) {
      tok = putback;
      putback = null;
    } else {
      skipWhitespace();
      int c = input.read();
      switch (c) {
      case -1: // EOF
        tok = new Token(TokenKind.EOF);
        break;
      case '1' : case '2' : case '3': case '4': case '5': 
      case '6': case '7': case '8': case '9': 
        input.unread(c);
        String s = readNumber();
        tok = new Token(TokenKind.NUMBER, s);
        break;
      case '+' :
        tok = new Token(TokenKind.PLUS);
        break;
      case '*' :
        tok = new Token(TokenKind.STAR);
        break;
      case '-' :
        tok = new Token(TokenKind.MINUS);
        break;
      case '(' :
        tok = new Token(TokenKind.LPAR);
        break;
      case ')' :
        tok = new Token(TokenKind.RPAR);
        break;
      default:
        Character o = (char)c;
        tok = new Token(TokenKind.ILLEGAL, o.toString());
      }
    }
    traceOut(tok.toString());
    return tok;
  }
  public void putbackToken(Token tok) {
    // 戻せるのはトークン1個
    assert (putback == null); // 上書きはダメ
    traceOut(">>" + tok);
    putback = tok;
  }
  private void skipWhitespace() throws IOException {
    int c;
    while (true) {
      c = input.read();
      if (c == -1) {
        break;
      }
      if (!Character.isWhitespace((char)c)) {
        input.unread(c);
        break;
      }
    }
  }
  private String readNumber() throws IOException {
    int c;
    StringBuilder sb = new StringBuilder();
    while (true) {
      c = input.read();
      if (c == -1) {
        break;
      }
      if (!Character.isDigit((char)c)) {
        input.unread(c);
        break;
      }
      sb.append((char)c);
    }
    return sb.toString();
  }

  private void traceOut(String msg) {
    if (debug)
      System.out.println(msg);
  }
}

/* === 構文ツリーのノード === */
class Node {
  public final String data;
  public Node(String data) {
    this.data = data;
  }
}

class BinaryOpNode extends Node {
  public Node left;
  public Node right;
  public BinaryOpNode(String data, Node left, Node right) {
    super(data);
    this.left = left;
    this.right = right;
  }
}

class UnaryOpNode extends Node {
  public Node operand;
  public UnaryOpNode(String data, Node operand) {
    super(data);
    this.operand = operand;
  }
}

class NumberNode extends Node {
  public NumberNode(String data) {
    super(data);
  }
}

/* === パーザー === */
class Parser {
  public boolean debug = true;

  private Lexer lexer;
  public Parser(Lexer lexer) {
    this.lexer = lexer;
  }

  public Node parse() throws IOException {
    return expressionData();
  }
  /* 式データ ::= 式 EOF */
  private Node expressionData() throws IOException {
    traceOut("expressionData");
    Node tree = null;
    // 式
    tree = expression();
    if (tree == null) return null; // ERROR
    // EOF
    Token tok = lexer.nextToken();
    if (tok.kind != TokenKind.EOF) return null; // ERROR
    return tree;
  }
  /* 式 ::= 加数 ('+' 式)? */
  private Node expression() throws IOException {
    traceOut("expression");
    Node tree = null;
    // 加数
    Node first = summand();
    if (first == null) return null; // ERROR
    // ('+' 式)?
    Token tok = lexer.nextToken();
    if (tok.kind == TokenKind.PLUS) {
      // 式
      Node rest = expression();
      if (rest == null) return null; // ERROR
      tree = new BinaryOpNode("+", first, rest);
    } else {
      // EMPTY
      tree = first;
      lexer.putbackToken(tok);
    }
    return tree;
  }
  /* 加数 ::= 因数 ('*' 加数)? */
  private Node summand() throws IOException {
    traceOut("summand");
    Node tree = null;
    // 因数
    Node first = factor();
    if (first == null) return null; // ERROR
    // ('*' 加数)?
    Token tok = lexer.nextToken();
    if (tok.kind == TokenKind.STAR) {
      Node rest = summand();
      if (rest == null) return null; // ERROR
      tree = new BinaryOpNode("*", first, rest);
    } else {
      tree = first;
      lexer.putbackToken(tok);
    }
    return tree;
  }
  /* 因数 ::= 数 | '-' 因数 | '(' 式 ')' */
  private Node factor() throws IOException {
    traceOut("factor");
    Node tree = null;
    Token tok = lexer.nextToken();
    switch (tok.kind) {
    case NUMBER:
      // 数
      return new NumberNode(tok.data);
    case MINUS:
      // 因数
      Node operand = factor();
      if (operand == null) return null; // ERROR
      return new UnaryOpNode("-", operand);
    case LPAR:
      // '(' 式 ')'
      Node exp = expression();
      if (exp == null) return null; // ERROR
      tok = lexer.nextToken();
      if (tok.kind == TokenKind.RPAR) {
        return exp;
      } else {
        return null; // ERROR
      }
    default:
      return null; // ERROR
    }
  }
  private void traceOut(String name) {
    if (debug)
      System.out.println("(" + name + ")");
  }
}   

/* === インタプリタ風メイン === */
public class ArithExp {
  private static boolean lexerDebug = false;
  private static boolean parserDebug = false;

  public static void main(String[] args) {
    // デバッグレベルの設定
    int firstIndex = 0;
    if (args.length > 0) {
      int n;
      try {
        n = Integer.parseInt(args[0]);
        if (n <= 0) {
          lexerDebug = false; parserDebug = false;
        } else if (n == 1) {
          lexerDebug = true; parserDebug = false;
        } else if (n == 2) {
          lexerDebug = false; parserDebug = true;
        } else if (n >= 3) {
          lexerDebug = true; parserDebug = true;
        }
        firstIndex++;
      } catch (Exception e) {}
    }
    // 入力の準備
    InputStream in = null;
    BufferedReader lines = null;
    try {
      if (args.length == firstIndex) {
        in = System.in;
      } else {
        in = new FileInputStream(args[firstIndex]);
      }
      lines = new BufferedReader(new InputStreamReader(in));
    } catch (Exception e) {
      System.err.println(e);
      System.exit(1);
    }
    // 解析の繰り返し
    String line = null;
    try {
      while (true) {
        line = lines.readLine();
        if (line == null) break;
        System.out.println("");
        System.out.println(line + " ==>");
        Reader reader = new StringReader(line);
        doParse(reader);
      }
    } catch (Exception e) {
      System.err.println(e);
      System.exit(1);
    }
  }

  private static void doParse(Reader reader) {
    Lexer lexer = new Lexer(new PushbackReader(reader));
    lexer.debug = lexerDebug;
    Parser parser = new Parser(lexer);
    parser.debug = parserDebug;
    Node tree = null;
    try {
      tree = parser.parse();
      if (tree == null) {
        System.out.println("Syntax Error.");
      } else {
        printTree(tree);
      }
    } catch (Exception e) {
      System.err.println(e);
      System.exit(1);
    }
  }

  // 以下、ツリー表示
  private static void printTree(Node root) {
    if (root == null) return;
    printNode(root, 0);
    System.out.println("");
  }
  private static void printNode(Node node, int indent) {
    if (node instanceof NumberNode) {
      doIndent(indent);
      System.out.print(node.data);
    } else if (node instanceof UnaryOpNode) {
      UnaryOpNode uop = (UnaryOpNode)node;
      doIndent(indent);
      System.out.println(uop.data + "(");
      printNode(uop.operand, indent + 1);
      System.out.println("");
      doIndent(indent);
      System.out.print(")");
    } else if (node instanceof BinaryOpNode) {
      BinaryOpNode bop = (BinaryOpNode)node;
      doIndent(indent);
      System.out.println(bop.data + "(");
      printNode(bop.left, indent + 1);
      System.out.println(",");
      printNode(bop.right, indent + 1);
      System.out.println("");
      doIndent(indent);
      System.out.print(")");
    } else {
      assert false;
    }
  }
  private static void doIndent(int indent) {
    for (int i = indent; i > 0; i--) {
      System.out.print("  ");
    }
  }
}