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

Computer organisation and architecture, design of parallel adder using 9''s... design of parallel adder using 9''s compliment

Transform to xhtml, While working in the eHealth Applied Research lab at Mo... While working in the eHealth Applied Research lab at Mohawk College, you are asked to transform an xml file into an XHTML representationusing XSLT for display in a browser.The xml

Matlab error, n2=2:100; t=3; while t { g3(t)=(1/2)*(0.63)*(0.8.... n2=2:100; t=3; while t { g3(t)=(1/2)*(0.63)*(0.8.^(n2)); t=t+1; } g3(1)=0; g3(2)=0; what is wrong with the code above? it tells me that line: g3(t)=(1/2)

Java, how to save bulk entries at a time using collections? how to save bulk entries at a time using collections?

Java applet assignment help, Objectives: Create an applet, Use metho... Objectives: Create an applet, Use methods from the Graphics class , Use the Color class General Instructions: The java class that need to be imported into this assignm

Algorithm to enumerate a fingerprint, Let S =  {s 1 , s 2 , .... , s k } de... Let S =  {s 1 , s 2 , .... , s k } denote a set of k genomes. The problem of fingerprinting is the task of identifying a shortest possible substring α i from each string si such t

Write an implementation for the prime machine, You should use the BToolkit ... You should use the BToolkit to produce the answers to the questions below. Where applicable, please use the machine names and identifier names suggested in the question to help me

Pseudo-code to illustrate the breakpoint in a program, The standard way for... The standard way for debuggers to plant interactive breakpoints in a program in RAM (whatever the processor instruction set) is to save the break pointed instruction and replace it

Shopping Cart, Shopping Cart Purpose – Allows user to browse while keeping ... Shopping Cart Purpose – Allows user to browse while keeping track of the items in which they will purchase at the end on the order page link and this will give a final price for al

Define call by value - computer programming, Define Call by value - Compute... Define Call by value - Computer Programming? Functions are raise by writing their name and an appropriate list of arguments within parenthesis. Usually these arguments are in t