##  Lin Jensen, 15 March 2002
##      revised 31 October 2003
##  for CSC 116 assembly class
##
##  Reverse polish (post-fix) caluclator, reads a string
##  Example (2 + 3) - 47 in postfix is " 2 3 + 47 -"
##  Example 2 + (3 - 47) in postfix is " 2 3 47 - +"
##
##  spaces are required to separate numbers, optional around operators
##
##  action on other characters is undefined, implementation will ignore
##
##  This version splits the program into two parts, 
##	getToken: uses a FSM to get a "token" either an integer or \n, + - * /
##							other chars ignored
##  		the two major states are: number in progress, or not.
##	calculate: while more tokens,
##		if integer, push on stack
##		else //operation
##		`	pop 2 numbers, operate, push result (stack shrinks by 1)
##
        .globl  __start
        .text
__start:

# -- test string for the function
        la      $a0, prompt     #some string should be input
        li      $v0, 4
        syscall
mainloop:                       #WHILE non-empty string
        la      $a0, sentence
        li      $a1, 82
        li      $v0, 8          #input a string containing an expression
	syscall
        lb      $t0, ($a0)
        beq     $t0,0xA,exitprogram   #newline means 'ENTER' pressed immediately
            jal     calculate

            move    $s0, $v0        #save result

            la      $a0, ans
            li      $v0, 4
            syscall

            move    $a0, $s0        #print result
            li      $v0, 1
            syscall
            la      $a0, endl
            li      $v0, 4
            syscall
            j mainloop
exitprogram:
        li      $v0, 10
        syscall                 #goodbye
##----------------------------------------------

getToken:
        sub     $sp, 16           # save registers
        sw      $ra,  ($sp)     # return address
        sw      $s0, 4($sp)     # use s0 for string pointer
        sw      $s1, 8($sp)     # use s1 for state
        sw      $s2,12($sp)     # use s2 for number
	move	$s0, $a0
        li      $s1, 1          # initial state
tokenloop:
        lb      $a0, ($s0)      # get character
        add     $s0, 1          # consume input
        bgt  $s1,1,state2
state1:
	jal	isdigit
	bnez   $v0, startnumber	# if digit, go to state 2 and start number
#  else check if endl or operator   
	   beqz	$a0,accept
	   beq	$a0,'+',accept   
	   beq	$a0,'-',accept   
	   beq	$a0,'*',accept   
	   beq	$a0,'/',accept   
	   j	tokenloop	#ignore any other character
   accept:
	   move $v0,$a0		# return the acceptable character
   	   li	$v1, 0		# return fact it is a character
	   j	returntoken
   startnumber:
	   li	$s1, 2		# switch to state 2
	   and	$s2, $a0,0x0f		# number sofar = ch - '0'
	   j    tokenloop		# space (or strange char) ignore (consume)

state2:
	jal	isdigit		# is it an additional digit?
	beqz   $v0, finishnumber   # no, push digit and go to state 1
		# yes, stay in state 2
#   appenddigit:
	   mul   $s2,$s2,10		# n = n*10
	   and	 $a0,0x0f		#   make digit binary
	   add   $s2,$s2,$a0		# n = n*10 + digit
	   j	tokenloop	
   finishnumber:	   
	   move	$v0, $s2	# return number
	   li	$v1, 1		# return integer flag
	   sub	$s0, 1		# BUT RETAIN NONDIGIT char. as unprocessed
	   			#"Sombody else's problem" for next call to getToken
returntoken:
	move	$a0, $s0	# advance callers $a0, to reflect "consumed" chars   
	lw      $ra,  ($sp)	# POP return address
        lw      $s0, 4($sp)
        sw      $s1, 8($sp)     # use s1 for state
        sw      $s2,12($sp)     # use s1 for state
        add     $sp, 16          # POP return address
        jr      $ra

#--- end getToken------------------------------------------------------
#------------------------------------------------------
calculate:
        sub     $sp,8           # save registers
        sw      $ra,  ($sp)     # return address
        sw      $fp, 4($sp)     #    fp to save original top of stack
        move    $fp, $sp        #     since we don't know if input is
                                #     well-formed
calcloop:                               #WHILE more tokens
	jal	getToken
	or	$t0,$v0,$v1	# endl character if both zero
	beqz	$t0, state3
	beqz	$v1, doOper
#  push number on stack
	   sub	$sp,4
	   sw	$v0,($sp)
	   j	calcloop
#  if operation, do it
   doOper:			#  fetch two operands from stack
	lw	$t2, ($sp)	# last in, first out is second value
	add	$sp, 4		# we are only releasing stack space for 1 word
	bge	$sp, $fp, empty	# check for our stack area EMPTY
	lw	$t1,($sp)	        # first value, space for storing push
	   bne	  $v0, '+', else1
		add  $t0,$t1,$t2	#  ADD them
		j    continue
   else1:
	   bne	 $v0, '-', else2
		sub  $t0,$t1,$t2	#  SUBTRACT them
		j    continue
   else2:
	   bne	 $v0, '*', else3
		mulo $t0,$t1,$t2	#  MULTIPLY them
		j    continue
   else3:
# 	   bne	 $v0, '/', otherwise  -- should be divide
		div  $t0,$t1,$t2	#  DIVIDE them
continue:
	   sw  $t0, ($sp)	# put result of op. back at top of stack
        j       calcloop
state3:
        lw     $t2, ($sp)       # return result from top of stack
	add    $sp, 4	
## ------------------------------------- ERROR checking added --------
extraloop:			#Possibly extra numbers were left on the stack,
        bge    $sp,$fp,calcexit  #WHILE more numbers left on the stack
	   lw    $a0,($sp)
	   add   $sp, 4		#POP and write them
	   li    $v0, 1
	   syscall
	   la    $a0,unpro
	   li    $v0,4
           syscall
	   j extraloop 

#----- exit code - restore saved register(s) ---------------
calcexit:
	move    $v0, $t2
        move    $sp, $fp        # remembered top of stack
        lw      $ra,  ($sp)
        lw      $fp, 4($sp)
        add     $sp, 8          # POP return address
        jr      $ra

##---------------------------------------------------------------------------
isdigit:                        #is the arg. a numeric char?
        slt     $t0, $a0,'0' 
        sgt     $t1, $a0, '9'
        nor	$v0, $t0,$t1    # true if neither too small NOR too big
	and	$v0, 1 		# only want 1 bit result
        jr      $ra

## ---------------------------------------------------------------------------
##  ERROR EXIT
empty:
	la	$a0,SEmess	# write stack empty message
	li	$v0,4
	syscall
	li	$v0,10
	syscall			# and exit program

        .data

#sentence: .asciiz "2 33 3 - 7+ +" #2+(33-3)+7=39
sentence: .space  84
prompt:	.asciiz "Type a (reverse) polish integer expression,\nuse space between numbers\nENTER to stop\n"
endl:   .asciiz "\n"
ans:    .asciiz " Evaluates to = "
SEmess: .asciiz "*** STACK EMPTY error: too many operators\n"
unpro:  .asciiz "\tunprocessed\n"

#---- end file polish.asm