## Description

Introduction

Stacks have many uses. They can be used to design a calculator to process numbers and math operators.

You are accustomed to seeing math expressions such as 3 + 4 in infix format where the operator (+) is in

between the operands (3 and 4). This format is easy to compute for the human user: for example, if you

see an expression 3 + 4 * 5, you know that first 4 should be multiplied by 5, and then 3 should be added

to the result. It is harder for a computer that reads input from left to right to follow the same steps. It

first reads 3, then reads “+” sign. When it encounters 4, it does not know whether any operation of

higher precedence is coming, so it may attempt to add 3 and 4 right away. The solution is to use a

special format called postfix notation where the operator comes after the operands so 3 + 4 becomes 3

4 +.

In this assignment, you will implement a Stack ADT as an extendable array to compute the answer to

arithmetic expressions in the postfix notation.

Converting Arithmetic Expression from Infix to Postfix Notation

For the purposes of this assignment you do not need to write a program to convert infix expression to

postfix. Your program will take the postfix expression as input, which you will accept from the user.

However, learning to convert from infix to postfix will we useful to you. First thing that you need to

understand is operator precedence and associativity. Precedence tells us which operator is more

important and gets computed first. In 3 + 4 * 5, the * has higher precedence than + so 4*5 = 20 gets

computed and then 3 + 20 = 23 gets computed. Similarly, 3 * 4 + 5 means 3 * 4 = 12 gets computed and

then 12 + 5 = 17 gets computed. Associativity tells us which operator is more important when both

operators have the same precedence. In 3 + 4 – 5, both operators have the same precedence so we

compute the answer from left to right (left associativity). The expression 3 + 4 – 5 means 3 + 4 = 7 and

CPSC 131 – Data Structures Concepts Spring 2015

Page 3 of 9

then 7 – 5 = 2. The precedence and associativity of the operators is preserved when we convert infix to

postfix.

Arithmetic expressions in infix notation can be easily converted by hand to postfix notation.

Consider the infix expression: 5 * 7 + 9 / 3

Step 1. Fully parenthesize the expression according to the order of precedence and associativity.

((5 * 7) + (9 / 3))

Step 2. For each set of ( ), move operator to the end of the closing parenthesis.

((5 7 *) (9 3 /) +)

Step 3. Remove all of the parentheses, which results in the below postfix version.

5 7 * 9 3 / +

Getting started

Download the file Assignment2.cpp from Titanium, in this file you will find the code for your Stack class

with some of the function prototypes that you will implement. For your help there is a slide set on

“evaluation of arithmetic expressions” posted on Titanium. Note that there are a lot of details to this

assignment; too many to simply start programming without any forethought. For your own benefit you

would want to plan your solution in pseudo code before you start to write your C++ code.

Operations to implement

(Note: To improve readability of your C++ code, you should define your member functions outside the

class using scope resolution operator.)

You will be coding your own Stack class implemented as an extendable array. Do NOT use the STL

Stack. Below are the functions to write, additionally you are free to write helper functions that you

may need.

OperandStack(int stackSize); Constructor to your stack class.

~OperandStack(); Destructor to your stack class.

int size() const; returns the number of elements in the stack.

bool isFull() const; checks for the full stack.

CPSC 131 – Data Structures Concepts

Page 4 of 9

bool isEmpty() const; checks for the empty stack.

double top() const; returns the element at the top of the stack

without removing it from the stack.

void push(double x); push a new element x on the stack. If the

stack is full then call the growStack function to increase the

capacity of the stack and then push the new element.

void pop(); removes the top element from the stack. Note that

this function does not return the removed element.

void growStack(int newCapacity); increases the capacity of the

stack. Note that this will require a deep copy of the current

stack into a bigger one.

Solving a postfix expression.

Algorithm to compute the solution to a postfix expression:

Examine each number and operator in the input.

o If it’s a number, push it onto the stack

o Otherwise (it must be an operator)

o Pop the stack and store the number as the right operand

o Pop the stack and store the number as the left operand

o Compute the value of “left operand OPERATOR right operand”

o Push the result onto the stack

The final result will be the last value on the stack. Pop the stack and return the result. Check

for the errors: If the stack has more than one element left and there are no more operators

OR the stack has one element left and there is at least one operator then signal an error.

Example: Solving postfix expression 3 5 1 – * [ infix equivalent: (3 * (5 – 1)) ].

Postfix (input)

3 5 1 – * Stack afterwards

3 3

5 3 5

1 3 5 1

– 3 4

* 12

CPSC 131 – Data Structures Concepts

Page 5 of 9

Lookup the slide set “evaluation of arithmetic expressions” on Titanium for additional examples and

possible error cases.

For the sake of simplicity, your program should perform only the following binary arithmetic

operations: Addition +, subtraction -, multiplication *, and division /. Optionally you are free to

enhance your program by adding more arithmetic operations like power, etc.

Your program only needs to work for an input postfix expression with operands that are single digit

integers in the range of 0 to 9. However, optionally you are free to enhance your program such that

it works for operands having multiple digits (lookup the narrative and the code on pages 1101-1103

of your C++ Early Objects 8th edition for ideas on working with multi digit numbers. The same code

has been posted on Titanium under the “Code” section as postfixToInfix.cpp).

C++ function to write: void solvePostfix(string postfixStr); computes the value

of an arithmetic expression given in postfix notation as an input string postfixStr. This function will

use the aforementioned algorithm to solve the postfix expression and print out the final result. From

your main function you may take the postifix expression as input from the user and pass it to the

solvePostfix as argument.

Below are some sample postfix input expressions that you could use to test your program:

Infix Postfix (input) Result

((8 * (2 + 3)) / 4) 8 2 3 + * 4 / 10

((8 / 2) + (3 * 4)) 8 2 / 3 4 * + 16

((8 + 5) / (9 – 7)) 8 5 + 9 7 – / 6.5

8 2 * 3 4 + error

8 2 * + 3 / error

You should include in your assignment report:

o Pseudo code for your function: void solvePostfix(string postfixStr);

o Include screen shots for below input and output.

Enter a postfix expression: 8 2 3 + * 4 /

Result: 10

CPSC 131 – Data Structures Concepts

Page 6 of 9

Enter a postfix expression: 8 2 / 3 4 * +

Result: 16

Enter a postfix expression: 8 5 + 9 7 – /

Result: 6.5

Enter a postfix expression: 8 2 * 3 4 +

Result: error – malformed expression

Enter a postfix expression: 8 2 * + 3 /

Result: error – malformed expression

What to hand in

A) Submit your C++ source code (cpp file). If you choose to work in pair, both students must

individually upload the cpp file via Titanium. Write yours and your partner’s name, section

number, and “Assignment 2” at the top of your cpp file as comments.

B) Submit a written report electronically as a PDF or MS Word doc file through Titanium. Again, if

you worked in pair then each student uploads the report individually. Write yours and your

partner’s name, section number, and “Assignment 2” on the first page of your report. Your

report should include:

1. Give pseudo code for each of those functions as previously asked in this document.

(Refer “additional notes” section of this document for tips on how to write good pseudo

code).

2. Screen shots of your input and output for each of those functions as previously asked in

this document. Note that typed or hand written input/output will not be considered.

You must provide screen shots of your actual program run.

3. Do not include any C++ code in the report. It is to be uploaded separately as a .cpp file

as asked in A).

CPSC 131 – Data Structures Concepts

Page 7 of 9

Additional Notes

Pseudo code

Word of caution: It may be tempting to jump into C++ coding and later convert it to some sort of

pseudo code. This is contrary to the purpose of writing pseudo code. If you find yourself in such a

situation then you are missing out on the benefits that result from detailed planning.

The idea behind pseudo code is that it is easier for people to understand than conventional

programming language code, and that it is an efficient and environment-independent description of

the key principles of your solution.

Another advantage is that pseudo code is a useful tool for planning your program design. It allows

you to sketch out the structure of your program and perform stepwise refinement before the actual

coding takes place.

Below is a sample pseudo code for the game of fizz buzz. It contains some programming language

elements augmented with high level English description. The goal is to have enough useful details

while leaving out elements not essential for human understanding of your program, like, variable

declaration and system specific code.

fizzbuzz()

Input: none

Return: none

for i <- 1 to 100 do
print_number <- true
if i is divisible by 3
print "Fizz"
print_number <- false
if i is divisible by 5
print "Buzz"
print_number <- false
if print_number == true
print i
print a newline
Pseudo code style that you follow for your program does not have to be exactly as above. You may
choose the style described in your textbook. In addition, there are numerous resources available on
the internet that describe various popular styles, feel free to look up and choose one.
CPSC 131 – Data Structures Concepts
Page 8 of 9
How detailed? Check for balance. If the pseudo code is hard for a person to read (too close to a
particular programming language’s syntax) or difficult to translate into working code, i.e., too vague,
(or worse yet, both!), then something is wrong with the level of detail you have chosen to use.
Code Writing: A bad approach is to write entire code all inside one function and later perform a
massive refactoring, i.e., split your code into multiple cohesive functions. It leads to increased effort
in integration, testing, and debugging. Good approach is to plan ahead and start by writing small
cohesive functions (up to a maximum of 30 lines or what might easily fit on one screen) with
reasonable refactoring of code as you go along.
Choice of loops: Choose appropriate loop type (for, while or do while) in a way that it makes your
program logic simpler and code more readable.
Testing: You should test each function as you code it. Use of big bang approach to testing, i.e.,
postponing to test after you have written all functions would make it very difficult to isolate errors
in your code.
Commenting your code
1. File comments: Start your cpp file with a description of your program, names of authors, date
authored, and version. Add other comments as asked in the “what to hand in” section of this
document.
2. Commenting function header: Right above the header of each of your function you should have
a comment. The comment will have three pieces to it:
Describe what the function accomplishes.
Inputs: Indicates what the required parameters are for the function. “nothing” for no
parameters.
Return: Clearly states what the function computes and returns. “nothing” for void
functions.
Here is an example:
CPSC 131 – Data Structures Concepts
Page 9 of 9
3. Section comments: Add comments for each section of your code within your function like
variable declaration, taking input, computation, display output, etc.
4. Explanatory comments should be added for tricky or complicated or important code blocks.
5. Line comments: Lines that are non-obvious should get a comment at the end of the line. These
end-of-line comments should be separated from the code by 2 spaces. Break long comments
into multiple lines.