Expression Tree, Programming Languages

Assignment Help:
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 - *

Related Discussions:- Expression Tree

We are need of a prestashop expert, We are need of a PrestaShop Expert W...

We are need of a PrestaShop Expert We are getting a fresh design created for our Jewellery website. This job is in 2 parts 1. The website engine is PrestaShop as well as w

How would you install a multiple layered security product, Problem: (i)...

Problem: (i) All Security authentication mechanism that run on the TRU64 Unix Operating system run under the Security Integration Architecture ( SIA ) layer. Explain with diag

Explain the comma operator- computer programming, Explain the Comma Operato...

Explain the Comma Operator- Computer Programming? The comma has two utilization and the most common use is as a parameter separator for data types and function parameter lists. H

Shell script to convert decimal no. to any other base no., Normal 0 ...

Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

I got a project and i need help , the details on the two pictures on the li...

the details on the two pictures on the link below : http://rak-up.com/up/files/18637.jpg ">http://rak-up.com/up/files/18636.jpg http://rak-up.com/up/files/18637.jpg

Program to reads a sequence of integer numbers , Task: This assignment...

Task: This assignment is about writing programmes and Web Services in C#: 1) Develop a console programme that reads a sequence of integer numbers from the console and sorts

Explain cascading style sheets, Question: (a) In JavaScript, the Windo...

Question: (a) In JavaScript, the Window Object is commonly used to request information from a user or to output some results. Give three ways how to create instances of the

Vb assignment, Design an application that opens and analyses word files. R...

Design an application that opens and analyses word files. Requirements: Create an application that analyses text documents. It should open a text file, read each word into an ap

Differentiate between high level and low level languages, The languages use...

The languages used in the module are of a type known as high-level languages. There is another set of languages known as low-level languages. (a) Differentiate between high-leve

Small code have missing part, #question. /* * * * * * * * * * * * * * * * *...

#question. /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Description: *

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd