Programming Assignment #3: Infix Expression Evaluation

Introduction

In this programming assignment you will write two evaluators for fully parenthesized infix expressions: one using stacks and one using recursion.

Functional Requirements

Your program must be in a file called infix.py. The program must read fully parenthesized infix expressions from the the user, one per line, evaluate them, and write the result to the terminal. It must evaluate them twice: once using stacks, and once using recursion. It must continue to evaluate expressions until the user enters an empty line. If it encounters erroneous input (a malformed expression), it must report an error and ask for more input.

The infix.py program must evaluate fully parenthesized integer expressions whose constants are single digits and whose operations are addition (+), subtraction (-), multiplication (*), integer division (/), and modular division (%). It must also recognize parentheses and skip whitespace (blanks and tabs).

Here is a sample execution of infix.py:

$ python infix.py
Infix expression evaluator.
> ((9+3) / (8-2))
2
2
> ((8=2)*5)
Bad characters.
> ((8+2)*5
Missing right parenthesis.
Missing right parenthesis.
> (8+2)*5))
Extra characters at end of expression.
Missing left parenthesis.
> 
Bye.
$ 

In this example, $ is the Unix prompt. Evaluators may give different error messages because of differences in the way that they detect errors.

Design Requirements.

The file infix.py must conform to the following skeleton. You should add additional helper functions, but the functions included below must be implemented in accordance with their docstrings. You should use the stack class defined in pyliststack.py to implement your stack-based evaluator.

"""
Header docstring should be here. 
"""    
from pyliststack import Stack
   
class BadExpressionError(Exception):
    pass 
        
        
def evalInfixStack(expression):
    """ Evaluate a fully parenthesized infix expression using a stack.

    This function evaluates fully parenthesized  expressions involving
    single digit integers and the operators addition (+), subtraction (-), 
    multiplication (*), integer division (/), and modular division (%).
    
    A BadExpressionError will be raised if the expression contains unrecognized
    characters, or is not well formed.  Spaces and tab characters are ignored.
    
    
    Arguments: expression - a string containing a mathematical expression.
    
    Returns: an integer containing the value of the expression. 
    """ 
    pass

def evalInfixRecursion(expression):
    """ Evaluate a fully parenthesized infix expression using recursion.

    This function evaluates fully parenthesized  expressions involving
    single digit integers and the operators addition (+), subtraction (-), 
    multiplication (*), integer division (/), and modular division (%).
    
    A BadExpressionError will be raised if the expression contains unrecognized
    characters, or is not well formed.  Spaces and tab characters are ignored.
    
    
    Arguments: expression - a string containing a mathematical expression.
    
    Returns: an integer containing the value of the expression. 
    """ 
    pass

def main():
    """ Prompt a user for mathematical expressions and print results twice: 
    once evaluated using a stack, and once evaluated using recursion. 
    """
    pass

  
   
if __name__ == "__main__":
    main()
        

You are not required to submit unit tests with this assignment, but I recommend that you write them anyway. Methodical testing is likely to save you time and effort in the long run.

Hints

• To make processing the characters from the input string easier when doing recursive evaluation, you should obtain a sting iterator and use it as your source of characters. For example, the following python functions recursively computes the length of a string:

  def recStringLength(string):
      strIter = iter(string)
      return recStringLengthInner(strIter, 0)
  
  def recStringLengthInner(strIter, length):
      try:
          ch = strIter.next()
      except StopIteration:
          #base case! the end of the string has been reached. 
          return length
      
      return recStringLengthInner(strIter, length + 1)
  

• Removing white space can be accomplished using the split and join methods of the string class.

• You will need to be able to check to see if individual characters are digits, operators, parentheses or unrecognized characters. The __contains__ method of the string class can be useful here. For example, the expression:

  s in "+-*/%"
  

  will evaluate to True if s is a string containing an operator.

  One way of checking to see if a string contains an integer is to attempt to cast the string to an integer inside a try catch block. If a value error is raised then you know that the string does not represent an integer:

  >>> int("house")
  Traceback (most recent call last):
    File "", line 1, in 
  ValueError: invalid literal for int() with base 10: 'house'
  

• You will probably find it helpful to have an evaluate function that takes an operator character and two integers as arguments and returns the result of applying the operator designated by the character to the integer arguments. For example: evaluate("*",2,3) returns 6.
• Correct error checking will only count for 10% of your grade for this assignment. Your initial focus should be on evaluating correctly formatted expressions.

Handing In

You should submit a single .py files through Blackboard before the deadline. There is no need to submit pyliststack.py. As always, your code should conform to the CS240 Python Coding Conventions.

Acknowledgments

This is a modified version of a project originally developed by Dr. Chris Fox.