Question

Tree and Preorder

For each expression, construct an expression tree, then print the preorder of the tree.

Write this in Java, test all cases below

7 * ( 3 - 6 ) + 5 => + * 7 - 3 6 5 13.0 +

18 / -4 => + 13.0 / 18 -4

0.11 / 5 * ( 0.2 * 7 ) => * / 0.11 5 * 0.2 7

-0.27 * 2.21 + 3 - -0.7 / -2

2.05 - 5 + 3 -3 - 1 + 2 + -3.4 / 5

Answer 1

solution:

class StackNode

{

public char data;

public StackNode leftChild;

public StackNode rightChild;

public StackNode(char x)

{

data = x;

}

public void displayNode()

{

System.out.print(data);

}

}

class Stack1

{

private StackNode[] a;

private int top, m;

public Stack1(int max)

{

m = max;

a = new StackNode[m];

top = -1;

}

public void push(StackNode key)

{

a[++top] = key;

}

public StackNode pop()

{

return (a[top--]);

}

public boolean isEmpty()

{

return (top == -1);

}

}

class Stack2

{

private char[] a;

private int top, m;

public Stack2(int max)

{

m = max;

a = new char[m];

top = -1;

}

public void push(char key)

{

a[++top] = key;

}

public char pop()

{

return (a[top--]);

}

public boolean isEmpty()

{

return (top == -1);

}

}

class Conversion

{

private Stack2 s;

private String input;

private String output = "";

public Conversion(String str)

{

input = str;

s = new Stack2(str.length());

}

public String inToPost()

{

for (int i = 0; i < input.length(); i++)

{

char ch = input.charAt(i);

switch (ch)

{

case '+':

case '-':

getOperator(ch, 1);

break;

case '*':

case '/':

getOperator(ch, 2);

break;

case '(':

s.push(ch);

break;

case ')':

gotParenthesis();

break;

default:

output = output + ch;

}

}

while (!s.isEmpty())

output = output + s.pop();

return output;

}

private void getOperator(char opThis, int prec1)

{

while (!s.isEmpty())

{

char opTop = s.pop();

if (opTop == '(')

{

s.push(opTop);

break;

} else

{

int prec2;

if (opTop == '+' || opTop == '-')

prec2 = 1;

else

prec2 = 2;

if (prec2 < prec1)

{

s.push(opTop);

break;

} else

output = output + opTop;

}

}

s.push(opThis);

}

private void gotParenthesis()

{

while (!s.isEmpty())

{

char ch = s.pop();

if (ch == '(')

break;

else

output = output + ch;

}

}

}

class Tree

{

private StackNode root;

public Tree()

{

root = null;

}

public StackNode getRoot() {

return root;

}

public void insert(String s)

{

Conversion c = new Conversion(s);

s = c.inToPost();

Stack1 stk = new Stack1(s.length());

s = s + "#";

int i = 0;

char symbol = s.charAt(i);

StackNode newNode;

while (symbol != '#')

{

if (symbol >= '0' && symbol <= '9' || symbol >= 'A'

&& symbol <= 'Z' || symbol >= 'a' && symbol <= 'z')

{

newNode = new StackNode(symbol);

stk.push(newNode);

} else if (symbol == '+' || symbol == '-' || symbol == '/'

|| symbol == '*')

{

StackNode ptr1 = stk.pop();

StackNode ptr2 = stk.pop();

newNode = new StackNode(symbol);

newNode.leftChild = ptr2;

newNode.rightChild = ptr1;

stk.push(newNode);

}

symbol = s.charAt(++i);

}

root = stk.pop();

}

public void preOrder(StackNode localRoot)

{

if (localRoot != null)

{

localRoot.displayNode();

preOrder(localRoot.leftChild);

preOrder(localRoot.rightChild);

}

}

}

public class Main

{

public static void main(String args[])

{

Tree tree = new Tree();

String exp1 = "7*(3-6)+5";

tree.insert(exp1);

tree.preOrder(tree.getRoot());

}

}

please give me thumb up