P1: CS 200 Data Structures and Algorithms (Spring 2015)

CS 200, Spring 2015
P1: Evaluating postfix expressions using a stack

Due and late dates and times

Due: February 11 23:59
Late: February 13 17:00

Overview

The object of this assignment is to exercise postfix expressions, scan them in, and evaluate then using a stack. Copy the following client code, starter Postfix code and input file:

EvalPost

This client code is provided and exercises your Postfix code. Don't change it. We will use other client codes in the testServer.

Evalpost gets the input filename from agrs[0]. If a second argument exists, debug is true, else false. EvalPost creates a scanner that reads lines from the file named in args[0] and instantiates a Postfix object for each line. It then calls the eval method in the Postfix object, and prints the result returned.

Postfix

This is the code you need to work on. The instance variables are:

private ArrayList evalStack.
The evaluation Stack.
private String nextToken.
For each Token (Integer or operator) from the scanner.
private Scanner scLine.
A scanner that has been given the input line in the constructor.
private boolean debug.
A boolean indicating debug mode.

Implement evalStack, a stack of Integers, with the methods push and pop. In the method eval, use pops and pushes to evaluate the postfix expression. You need to at least implement the following methods (you may want to create helper methods):

private void push(Integer i)
Push Integer i on evalStack. In debug mode print "push: " + pushed value.
private Integer pop()
Pop Integer from evalStack. If the evalStack is empty, return null. In debug mode print "pop: " + popped value.
public Integer eval()
Evaluate the postfix expression in scLine. Postfix expressions contain tokens, in our case Integers and operators. Tokens in a postfix expression are delimited by spaces. When encountering an Integer, push it on the evalStack. When encountering an operator, pop two values off the evalStack (right, then left), perform the operation, and push the result on the evalStack. At the end of the expression, pop the result off the stack and return it. scLine either contains an empty line, or a valid postfix expression, so you don't need to worry about invalid expressions.

Testing and submitting your code

resDB contains the result for input file in, when in debug mode.
res contains the result for input file in, when not in debug mode.