For this exercise you will be determining the derivative of a single-variable al
ID: 3721866 • Letter: F
Question
For this exercise you will be determining the derivative of a single-variable algebraic function. You will not be calculating the derivative just printing it out. You will be doing this in three steps. Each step will be a separate assignment. You can work in pairs of two for each problem set.
Problem Set 5a [20 points]
For this assignment you will write a method that takes in "fully-parenthesized" string and creates a parse tree and prints the parse tree out. The parse tree should be a binary tree with the nodes that contain the normal data, left, right, and parent fields.
Assumptions:
1. The input string is "fully-parenthesized".
2. The input string contains only: +, -, /, *, ^, x, X, (, ), 0-9.
3. Use the parent field. Do not use a stack to keep track of the parents.
4. You can use the algorithm in section 6.5.1 and the Listing 6.9 to help you get started. It won't be the same but it will be very close.
5. All input strings are correctly written.
the code is has to be written in python
Explanation / Answer
class Et:
# Constructor to create a node
def __init__(self , value):
self.value = value
self.left = None
self.right = None
# A utility function to check if 'c'
# is an operator
def isOperator(c):
if (c == '+' or c == '-' or c == '*'
or c == '/' or c == '^'):
return True
else:
return False
# A utility function to do inorder traversal
def inorder(t):
if t is not None:
inorder(t.left)
print t.value,
inorder(t.right)
# Returns root of constructed tree for
# given postfix expression
def constructTree(postfix):
stack = []
# Traverse through every character of input expression
for char in postfix :
# if operand, simply push into stack
if not isOperator(char):
t = Et(char)
stack.append(t)
# Operator
else:
# Pop two top nodes
t = Et(char)
t1 = stack.pop()
t2 = stack.pop()
# make them children
t.right = t1
t.left = t2
# Add this subexpression to stack
stack.append(t)
# Only element will be the root of expression tree
t = stack.pop()
return t
# Driver program to test above
postfix = "ab+ef*g*-"
r = constructTree(postfix)
print "Infix expression is"
inorder(r)
class Et:
# Constructor to create a node
def __init__(self , value):
self.value = value
self.left = None
self.right = None
# A utility function to check if 'c'
# is an operator
def isOperator(c):
if (c == '+' or c == '-' or c == '*'
or c == '/' or c == '^'):
return True
else:
return False
# A utility function to do inorder traversal
def inorder(t):
if t is not None:
inorder(t.left)
print t.value,
inorder(t.right)
# Returns root of constructed tree for
# given postfix expression
def constructTree(postfix):
stack = []
# Traverse through every character of input expression
for char in postfix :
# if operand, simply push into stack
if not isOperator(char):
t = Et(char)
stack.append(t)
# Operator
else:
# Pop two top nodes
t = Et(char)
t1 = stack.pop()
t2 = stack.pop()
# make them children
t.right = t1
t.left = t2
# Add this subexpression to stack
stack.append(t)
# Only element will be the root of expression tree
t = stack.pop()
return t
# Driver program to test above
postfix = "ab+ef*g*-"
r = constructTree(postfix)
print "Infix expression is"
inorder(r)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.