Answer to Question #268149 in C for Neil

Question

Write a program to create an expression tree for a entered (by the user) postfix expression and traverse the tree to check the correctness.

Answer 1

#include<stack>
#include<iostream>
#include<string.h>
using namespace std;




struct ExpressionTree
{
	char item;
	ExpressionTree * leftTree, *rightTree;
};




bool isOperator(char ch)
{
	if (ch == '+' || ch == '-' ||
			ch == '*' || ch == '/' ||
			ch == '^')
		return true;
	return false;
}




void traversal(ExpressionTree *tree)
{
	if(tree)
	{
		traversal(tree->leftTree);
		printf("%c ", tree->item);
		traversal(tree->rightTree);
	}
}


ExpressionTree* new_node(char v)
{
	ExpressionTree *tempNode = new ExpressionTree;
	tempNode->leftTree = tempNode->rightTree = NULL;
	tempNode->item = v;
	return tempNode;
};




ExpressionTree* construct_Tree(char post_fix[])
{
	stack<ExpressionTree *> stack1;
	ExpressionTree *t, *t1, *t2;


	
	for (int i=0; i<strlen(post_fix); i++)
	{
		
		if (!isOperator(post_fix[i]))
		{
			t = new_node(post_fix[i]);
			stack1.push(t);
		}
		else
		{
			t = new_node(post_fix[i]);


		
			t1 = stack1.top(); 
			stack1.pop();	 
			t2 = stack1.top();
			stack1.pop();


			
			t->rightTree = t1;
			t->leftTree = t2;


			
			stack1.push(t);
		}
	}


	
	t = stack1.top();
	stack1.pop();


	return t;
}


int main()
{
	char str[] = "ab+ef*g*-";
	ExpressionTree* tree = construct_Tree(str);
	printf("Traversal of expression is \n");
	traversal(tree);
	return 0;
}