Programming Project #3

Assigned 11/7/95

Due Monday, 12/4/95 at 11:59pm

Introduction

The main purpose of this project is to integrate what you have learned in the two previous labs into a larger program.

RPN Calculator

A RPN (Reverse Polish Notation) Calculator is a calculator that takes arithmetic expressions in postfix form. HP calculators use a specific type of postfix.

Assignment

Write a function rpn in MIPS assembly language that processes an ASCII string containing an arthmetic expression in postfix form. Your function should take one argument str that is a pointer to the address containing the string. This argument should be passed in register $a0. The function should return two values. The final value left on the stack should be returned in $v0 (if possible), and an error code should be returned in $v1. The error codes are defined below.

Your calculator should accept ASCII character strings as input. An input string may contain integers and/or operators separated by whitespace. Remember that whitespace can be a space, a tab, or any combination of the two characters. The RPN calculator does operations on the string as follows: The string should be parsed from left to right. When you reach a number, push it onto the stack. If you reach an operator, normally you will pop values off the stack, do the computation, and push the result back on the stack. For purposes of parsing the string, you may assume that there is whitespace between each and every number and operator. You may also parse strings that that do not have whitespace between numbers and operators or between operators if it is easier for you, but note that you must somehow distinguish between a minus sign and a subtraction sign.

Your calculator should support the following operations:

"+" Pops the two top values at the top of the stack, adds them, and pushes the sum back onto the stack.

"-" Pops the two top values at the top of the stack, subtracts the next-to-top value from the top value, and pushes the difference back onto the stack.

"*" Pops the two top values at the top of the stack, multiplies them, and pushes the product back onto the stack.

"/" Pops the two top values at the top of the stack, performs an integer division, and pushes the quotient back onto the stack.

"f" Pops the top value at the top of the stack, finds the fibonacci sequence number corresponding to the value, and pushes the fibonacci number back onto the stack. Note that this is a lower-case "f".

"=" Peeks at all the values currently on the stack, by printing all the values on the stack, starting at the bottom of the stack and ending at the top.

You should use the syscall read_str to read in the ASCII expression string in the main portion of your program. You should then pass this string to your RPN function which should then perform the operations specified by the string. Use a modified version of your ASCII-to-binary function from lab #1 to convert the ASCII numbers to integers. Also use your fibonacci function from lab #2 to do fibonacci calculations.

The program you write should be structured as follows:

Main procedure
Read in expression
Pass string to rpn function
Print out resulting value or error message if error returned
Keep reading in expressions until an empty string is entered
rpn function and helper functions
Parse the string and do operations specified
Return the final value on the stack and an error code.

You should handle the following errors:

rpn error value ($v1)Error type
0 Valid return value
1Invalid Input
2Stack Underflow
3 Division by Zero
4More than one value left on stack

You do not need to worry about arithmetic overflows or underflows. If an error occurs, you should make sure you reset the stack to be empty. You should also make sure to reset the stack to empty after every function call. Set up the frame pointer and use it to determine where the stack pointer was before values were pushed onto it.

Here is an example run for the program:

Enter an expression: 8 5 * 10 6 - /
Result = 10
Enter an expression: -10 4 5 8 - + +
Result = -9
Enter an expression: 4 3 2 1 = + * = -
Stack = 4 3 2 1
Stack = 4 9
Result = -5
Enter an expression: 2 5 + f 3 -
Result = 10
Enter an expression: 10 + 5 2
Stack Underflow!
Enter an expression: 10 5 = a +
Stack = 10 5
Invalid Expression
Enter an expression:
Put this problem in its own file named rpn.s in the directory elec320/lab3 in your home directory. Also, to prove that your function works correctly, execute your function using 10 different sets of strings (each utilizing a few different operators) and place the output in a file called rpn.out. Please make a file called README in that directory that details anything you think might be helpful to the graders. This includes any assumptions you have made and a list of any problems with your lab. Last of all, make sure you comment this problem in the same manner specified for Projects 1 and 2.

Your function must be written to work under XSPIM on the owlnet SUN Sparc computers. We will check them for correctness in that environment. You may develop your program on other platforms, but in that case, you should test it on a SUN before turning it in for grading.