Part 1 ------ Note that the LeafNode class already shows the solution for its postfix() method. postfix() simply returns a string version of itself. To do this, it calls str on itself. str calls __str__, which returns the _data field converted to a string. The LeafNode infix() method does the same things as postfix(). Part 2 ------ The LeafNode prefix() method does the same things as postfix(). Part 3 ------ The LeafNode value() method simply returns the _data field. Make sure to refer to this field using the provided "self" object reference. Part 4 ------ Note that the InteriorNode class already shows the solution for its postfix() method. postfix() returns a string of the form: postfix of its left operand a space postfix of its right operand a space its operator Note that this pattern results in a recursive descent of the expression tree. The InteriorNode infix() method should use the following similar pattern: a left parenthesis "(" infix of its left operand a space its operator a space infix of its right operand a right parenthesis ")" Part 5 ------ The InteriorNode prefix() method should use the following pattern: its operator a space prefix of its left operand a space prefix of its right operand Part 6 ------ The InteriorNode value() method should use the following steps: Use self._leftOperand.value() to get the value of its left operand. Use self._rightOperand.value() to get the value of its right operand. self._operator contains the operator type. The valid operator types are: "+", "-", "*", "/", and "^". Use self._operator in conditional logic to calculate the value to return. Examples: If the operator is "+" (addition), the returned value should be: value of left operand + value of right operand If the operator is "^" (exponentiation), the returned value should be: value of left operand ** value of right operand If the operator does not equal a valid value, return 0.

~~~~~~~~~~~~~~~~~~~

"""
Expression tree nodes.
 
Source: Textbook chapter 10 Parsing and Expression Trees case study student files.
"""
 
class LeafNode(object):
 """Represents an integer."""
 
 def __init__(self, data):
 self._data = data
 
 def __str__(self):
 return str(self._data)
 
 # Part 1:
 def infix(self):
 # 
 
 # Part 2:
 def prefix(self):
 # 
 
 def postfix(self):
 return str(self)
 
 # Part 3:
 def value(self):
 # 
 
class InteriorNode(object):
 """Represents an operator and its two operands."""
 
 def __init__(self, op, leftOper, rightOper):
 self._operator = op
 self._leftOperand = leftOper
 self._rightOperand = rightOper
 
 # Part 4:
 def infix(self):
 # 
 
 # Part 5:
 def prefix(self):
 # 
 
 def postfix(self):
 return self._leftOperand.postfix() + " " + \
 self._rightOperand.postfix() + " " + \
 self._operator
 
 # Part 6:
 def value(self):
 # 
 
# A simple tester program:
def main():
 a = LeafNode(4)
 b = InteriorNode('+', LeafNode(2), LeafNode(3))
 c = InteriorNode('*', a, b)
 c = InteriorNode('^', c, b) 
 print("Expect ((4 * (2 + 3) ^ (2 + 3)):", c.infix())
 print("Expect ^ * 4 + 2 3 + 2 3 :", c.prefix())
 print("Expect 4 2 3 + * 2 3 + ^ :", c.postfix())
 print("Expect 3200000 :", c.value())
 
if __name__ == "__main__":
 main()
~~~~~~~~~~~~~~~~
""" View for the infix expression parser. Handles user interaction. Source: Textbook chapter 10 Parsing and Expression Trees case study student files. """ from parsers import Parser class ParserView(object): def run(self): parser = Parser() while True: sourceStr = input("Enter an infix expression: ") if sourceStr == "": break try: tree = parser.parse(sourceStr) print("Prefix:", tree.prefix()) print("Infix:", tree.infix()) print("Postfix:", tree.postfix()) print("Value:", tree.value()) except Exception as e: print("Error:") print(e) ParserView().run() 
~~~~~~~~~~~~~~~~~
""" Infix expression parser. Uses a recursive descent strategy. Source: Textbook chapter 10 Parsing and Expression Trees case study student files. """ from tokens import Token from scanner import Scanner from expressiontree import LeafNode, InteriorNode class Parser(object): def parse(self, sourceStr): self._completionMessage = "No errors" self._parseSuccessful = True self._scanner = Scanner(sourceStr) tree = self._expression() self._accept(self._scanner.get(), Token.EOE, "symbol after end of expression") return tree def parseStatus(self): return self._completionMessage def _accept(self, token, expected, errorMessage): if token.getType() != expected: self._fatalError(token, errorMessage) def _expression(self): tree = self._term() token = self._scanner.get() while token.getType() in (Token.PLUS, Token.MINUS): op = str(token) self._scanner.next() tree = InteriorNode(op, tree, self._term()) token = self._scanner.get() return tree def _factor(self): tree = self._primary() token = self._scanner.get() if token.getType() == Token.EXPO: op = str(token) self._scanner.next() tree = InteriorNode(op, tree, self._factor()) token = self._scanner.get() return tree def _fatalError(self, token, errorMessage): self._parseSuccessful = False self._completionMessage = "Parsing error -- " + \ errorMessage + \ " Expression so far = " + \ self._scanner.stringUpToCurrentToken() raise Exception(self._completionMessage) def _primary(self): token = self._scanner.get() if token.getType() == Token.INT: tree = LeafNode(token.getValue()) self._scanner.next() elif token.getType() == Token.L_PAR: self._scanner.next() tree = self._expression() self._accept(self._scanner.get(), Token.R_PAR, "')' expected") self._scanner.next() else: tree = None self._fatalError(token, "bad primary") return tree def _term(self): tree = self._factor() token = self._scanner.get() while token.getType() in (Token.MUL, Token.DIV): op = str(token) self._scanner.next() tree = InteriorNode(op, tree, self._factor()) token = self._scanner.get() return tree 
~~~~~~~~~~~~~~~~
""" Language processing scanner. Source: Textbook chapter 10 Parsing and Expression Trees case study student files. """ from tokens import Token class Scanner(object): EOE = ';' # end-of-expression TAB = '\t' # tab def __init__(self, sourceStr): self._sourceStr = sourceStr self._getFirstToken() # Returns Token.EOE when the string has been scanned. def get(self): return self._currentToken def hasNext(self): return self._currentToken != Token.EOE def next(self): temp = self._currentToken self._getNextToken() return temp def stringUpToCurrentToken(self): return self._sourceStr[0:self._index + 1] def _getFirstToken(self): self._index = 0 self._currentChar = self._sourceStr[0] self._getNextToken() def _getInteger(self): num = 0 while True: num = num * 10 + int(self._currentChar) self._nextChar() if not self._currentChar.isdigit(): break return num def _getNextToken(self): self._skipWhiteSpace() if self._currentChar.isdigit(): self._currentToken = Token(self._getInteger()) elif self._currentChar == Scanner.EOE: self._currentToken = Token(';') else: self._currentToken = Token(self._currentChar) self._nextChar() def _nextChar(self): if self._index >= len(self._sourceStr) - 1: self._currentChar = Scanner.EOE else: self._index += 1 self._currentChar = self._sourceStr[self._index] def _skipWhiteSpace(self): while self._currentChar in (' ', Scanner.TAB): self._nextChar() # A simple tester program: def main(): while True: sourceStr = input("Enter an expression: ") if sourceStr == "": break scanner = Scanner(sourceStr) token = scanner.get() while token.getType() != Token.EOE: print(token) scanner.next() token = scanner.get() if __name__ == '__main__': main() 
~~~~~~~~~~~~~~~~~~~~
""" Tokens for processing expressions. Source: Textbook chapter 10 Parsing and Expression Trees case study student files. """ class Token(object): UNKNOWN = 0 # unknown EOE = 1 # end-of-expression L_PAR = 2 # left parenthesis R_PAR = 3 # right parenthesis INT = 4 # integer MINUS = 5 # minus operator PLUS = 6 # plus operator MUL = 7 # multiply operator DIV = 8 # divide operator EXPO = 9 # power operator FIRST_OP = 5 # first operator code def __init__(self, value): if type(value) == int: self._type = Token.INT else: self._type = self._makeType(value) self._value = value def __str__(self): return str(self._value) def getType(self): return self._type def getValue(self): return self._value def isOperator(self): return self._type >= Token.FIRST_OP def _makeType(self, ch): if ch == '*': return Token.MUL elif ch == '/': return Token.DIV elif ch == '+': return Token.PLUS elif ch == '-': return Token.MINUS elif ch == '(': return Token.L_PAR elif ch == ')': return Token.R_PAR elif ch == '^': return Token.EXPO elif ch == ';': return Token.EOE else: return Token.UNKNOWN; # A simple tester program: def main(): plus = Token("+") minus = Token("-") mul = Token("*") div = Token("/") unknown = Token("#") anInt = Token(34) print(plus, minus, mul, div, unknown, anInt) if __name__ == '__main__': main() 
~~~~~~~~~~~~~~~~~
Output
 
Enter an infix expression: 7 - 2 * 5 Prefix: - 7 * 2 5 Infix: (7 - (2 * 5)) Postfix: 7 2 5 * - Value: -3 Enter an infix expression: (7 - 2) * 5 Prefix: * - 7 2 5 Infix: ((7 - 2) * 5) Postfix: 7 2 - 5 * Value: 25 Enter an infix expression: 9 * 5 + 10 Prefix: + * 9 5 10 Infix: ((9 * 5) + 10) Postfix: 9 5 * 10 + Value: 55 Enter an infix expression: 6 + 5 - 2 + 3 Prefix: + - + 6 5 2 3 Infix: (((6 + 5) - 2) + 3) Postfix: 6 5 + 2 - 3 + Value: 12 Enter an infix expression: 5 * 7 ^ 2 Prefix: * 5 ^ 7 2 Infix: (5 * (7 ^ 2)) Postfix: 5 7 2 ^ * Value: 245 Enter an infix expression: (4 * (2 + 3) ^ (2 + 3) Error: Parsing error -- ')' expected Expression so far = (4 * (2 + 3) ^ (2 + 3) Enter an infix expression: 4 * (2 + 3) ^ (2 + 3) Prefix: * 4 ^ + 2 3 + 2 3 Infix: (4 * ((2 + 3) ^ (2 + 3))) Postfix: 4 2 3 + 2 3 + ^ * Value: 12500 Enter an infix expression: >>>