"""

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:

>>>