CareerCup

I think what the question means if - if you are given an infix/postfix expression, make an expression tree out of it.

Eg. Convert a postfix expression into an expression tree

Algorithm:

1. Intialize a stack to store binary tree nodes.
2. Read the array from left to right.
3. If you come across an operand, make a node out of it and push into the stack.
If its an operator, pop two nodes from the stack and first popped node would be the operator node's right child and the second popped node would be the operator node's left child. Push the operator node into the stack
4.The last popped node would be the head of the tree.

struct node *createTree(int a[])
{
Stack S;
struct node *new = NULL;
for(int i = 0; a[i]! = ‘\0’; i++)
{
  if (arr[i] == ‘+’ || arr[i] == ‘-’ || arr[i] == ‘/’ || arr[i] == ‘*’)
  {
	new = newNode(a[i]);
	new -> right = s1.pop();
	new->left = s1.pop();
	s1.push(new);
  }
  else
  	s1.push(newNode(a[i]);
}
}
return s1.pop();
}

If you are talking about how will you represent this in OO-world, then the answer is using Composition design pattern which is structural.

I didn't understand the question.. could someone provide more info...

Expression Tree is ( math or regular)..
Example: a+b +ab can be represented in a binary tree.

Design: A simple binary tree will do for Math Expression taking the inpifx

I think the question is not about data structure to be used for expression tree but a design for it.

I can think of a following class structure:

abstract class Node{
}

class OperatorNode extends Node{
     Node leftNode;
     Node rightNode;
     int operator;//constants for +,-,*,/
}

class OperandNode extends Node{
     int number;
}
}