Question

Write a simple java program that takes input from the user as a fully parenthesized expression and converts it to a binary tree. Ex: (1+2 * (6-4)) or (A+B / (D-C))

When the tree is built, it should print the tree in some way.

Answer 1

import java.util.Stack; class Node { char value; Node left, right; Node(char item) { value = item; left = right = null; } } class ExpressionTree { boolean isOperator(char c) { if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^') { return true; } return false; } void inorder(Node t) { if (t != null) { inorder(t.left); System.out.print(t.value + " "); inorder(t.right); } } Node constructTree(char postfix[]) { Stack<Node> st = new Stack(); Node t, t1, t2; for (int i = 0; i < postfix.length; i++) { if (!isOperator(postfix[i])) { t = new Node(postfix[i]); st.push(t); } else { t = new Node(postfix[i]); t1 = st.pop(); t2 = st.pop(); t.right = t1; t.left = t2; st.push(t); } } t = st.peek(); st.pop(); return t; } } public class Main { public static void main(String[] args) { ExpressionTree et = new ExpressionTree(); String postfix = "(1+2*(6-4))"; char[] charArray = postfix.toCharArray(); Node root = et.constructTree(charArray); System.out.println("infix expression is"); et.inorder(root); } }