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

Describe url and hostname part, Describe URL and hostname part? The hos... Describe URL and hostname part? The hostname part of the URL should be a valid Internet hostname. It can also be an IP address like as 204.29.207.217 or 128.235.252.184. The

Recursive decent parser, Given grammar Grammar M following: 1 - - > b... Given grammar Grammar M following: 1 - - > begin end 2 - - > 3 - - > 4 - - > ? 5 - - > Id : = ; 6 - - > read ( ) ; 7 - - > write ( )

Java, what is the difference between class and interface what is the difference between class and interface

Write a perl script to assign letter grades to the students, Tasks: Writ... Tasks: Write a Perl script assignGrades.pl to assign letter grades to the students. Please use the classList2.txt file. Upon invoking, the script will access the file classL

Algorithem for create game application, Play is as follows: 1.) Player p... Play is as follows: 1.) Player places a bet a. Bet is on one of three choice i. "Player" will win ii. "Banker" will win iii. Tie between the "Player" and the "Banker

Create proptotype of student management system, XYZ International is a larg... XYZ International is a large Institute; Management in this institute wants to create Proper Student management System. There for they contact you and asked you to create Propto typ

Java, Write a program that repeatedly prompts for and reads a positive inte... Write a program that repeatedly prompts for and reads a positive integer value n and then calculates and displays the nth Fibonacci number

Matlab, i have a=[0 1 1 2 2 3 6 7 0 4 ] i want to delent elemet but keep it... i have a=[0 1 1 2 2 3 6 7 0 4 ] i want to delent elemet but keep its position i.e a(4)=[] it gives me 0 1 1 2 3 6 7 0 4 but i need 0 1 1 [] 2 3 6 7 0 4

Create procedures for accessing the root, (a)  Create procedures for access... (a)  Create procedures for accessing the root, left subtree and right subtree, and also mutators for changing the root, left subtree and right subtree of an avl argument. (b) Wr

Built a liner program to manage a staff, A manager at the local Walmart nee... A manager at the local Walmart needs to determine how many workers to hire to cover a 24-hour period. Each worker must work 9 consecutive hours but may only start work at the begin