For this assignment you will read a file expression.txt and create an expression tree. The expression will be a valid infix expression with the all the necessary parentheses so that there is no ambiguity in the order of the expression. You will evaluate the expression and print the result. You will also write the prefix and postfix versions of the same expression without any parentheses.

In an expression tree the nodes are either operators or operands. The operators will be in the set [''+'', ''-'', ''*'', ''/'']. The operands will be either integers or floating point numbers. All the operand nodes will be leaves of the expression tree. All the operator nodes will have exactly two children.

The outline of your program will be as follows:

class Stack (object):

class Node (object):

class Tree (object):
def __init__ (self):

def createTree (self, expr):

def evaluate (self, aNode):

def preOrder (self, aNode):

def postOrder (self, aNode):

def main():

main()
The function createTree() will take as input parameter an infix expression with parentheses as a String and create an Expression Tree from it. Assume that the expression string is valid.

You will take the expression string and break it into tokens. There are four different kinds of tokens - left parenthesis, right parenthesis, operator, and operand. When we read a left parenthesis we are starting a new expression and when we read a right parenthesis we are ending an expression. Here is the algorithm that you will use:

If the current token is a left parenthesis add a new node as the left child of the current node. Push current node on the stack and make current node equal to the left child.
If the current token is an operator set the current node''s data value to the operator. Push current node on the stack. Add a new node as the right child of the current node and make the current node equal to the right child.
If the current token is an operand, set the current node''s data value to the operand and make the current node equal to the parent by popping the stack.
If the current token is a right parenthesis make the current node equal to the parent node by popping the stack if it is not empty.
For the input file this is what your program will output:

( ( 8 + 3 ) * ( 7 - 2 ) ) = 55

Prefix Expression: * + 8 3 - 7 2

Postfix Expression: 8 3 + 7 2 - *

Posted Date: 4/20/2012 9:52:36 AM | Location : United States

Ask an Expert

Related Discussions:- Expression Tree, Assignment Help, Ask Question on Expression Tree, Get Answer, Expert's Help, Expression Tree Discussions

Write discussion on Expression Tree
Your posts are moderated

Write your message here..

Related Questions

What is jvm-java virtual machine, What is JVM-Java Virtual Machine  A J... What is JVM-Java Virtual Machine  A JVM stands for java virtual machine. This is virtual computer or an abstract computer that runs the complied java programs. In fact JVM is

C++, You are to write a program which will answer a pair of questions for s... You are to write a program which will answer a pair of questions for squares, triangles, circles and ellipses. A square is defined by its lower left corner (SLLx,SLLy), and the len

Write a shell script to find the maximum of three numbers, W.A.S.S to find ... W.A.S.S to find the maximum of three numbers Program # W.A.S.S to find the maximum of three numbers echo "Enter three No.:" read no1 read no2 read no3 if test $no1 -gt $n

Programs for shell scripts, 1. Write a bash shell script which searches thr... 1. Write a bash shell script which searches through your folders for files with the extension *.tex, and then interactively deletes the corresponding *.aux, *.dvi and *.log files (

Real distinct eigenvalues, Real Distinct Eigenvalues Under this case w... Real Distinct Eigenvalues Under this case we'll have the real, distinct eigenvalues l 1 ≠l 2 ≠l 3 a and their related eigenvectors, ?h 1 , ?h 2 and  ?h 3   are guarantee

Write a program to use a robot to move, Write a program to use a robot to m... Write a program to use a robot to move the stack of blocks from a source location to a target location, based. Movement of robot arms, picking and dropping, can be controlled usi

Complementary slackness and duality, Consider the following LP problem: ... Consider the following LP problem: min x 1 +3 x2 +x 3 -x 4 s.t. x 1 +x 2 +x 3 +x 4 ≥ 0 x 1 +x 2 -x 3 -x 4 ≥ 1 x 2 , x 3 ≥ 0 x 1 , x 4 ≤ 0. 1. Unique pr

Define an example of switch statement, Define an Example of Switch Statemen... Define an Example of Switch Statement? estimate(number) int number; /* Estimate a number as none, one, two, several, many */ {       switch(number) { case 0 :

Pattern matching program in xhtml, Part 1 Given the following Regular Exp... Part 1 Given the following Regular Expressions, explain in detail the pattern accepted by each. Pay attention to all the characters being used. Your answers need not appear with

A Simple Distributed Computing Platform , You are asked to develop a replic... You are asked to develop a replicator (client) that distributes a large job over a number of computers (a server group) on a single switched LAN (our BU04 lab). In this assignment,