To acquire expertise in stack manipulation and management, subroutine linkage and return conventions, and recursive procedures.
You are to reuse the postfix representation of the input and create an expression tree. Your MIPS program should make use of the expression tree to store the input and provide, by means of an adequate traversal, the value for the expression. Your solution should be structured according to the following steps:
Step 1: Convert expression from infix to postfix. Programming assignment 1 has already solved this step.
Step 2: Create a binary tree (expression tree) from the postfix representation of the input.
Step 3: Compute the value for the expression by means of an adequate tree traversal.
The expressions must be fully parenthesized and include the following operators:
1. + (addition)
2. - (subtraction)
For simplicity all numbers in the expression will have only one base ten digit, (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), in them. Your program must be composed of four states: input, convert-to-postfix, evaluate, and output states. You may reuse both input and convert-to-postfix components you have developed for programming assignment 2. At the evaluate state your solution constructs an expression tree and evaluates the expression by means of a tree traversal. At the output state your code must display the complete expression in the postfix notation followed by the = symbol and the expression’s numeric result.
Some valid expressions and their corresponding postfix notations are:
a) ((1-3)+5) corresponds to 13-5+ in postfix notation
b) (1-(3+5)) corresponds to 135+- in postfix notation
Shown below is the Console display for expression item a) above:
Expression to be evaluated:
((1 - 3) + 5)
13-5+ = 3
Consider a set of all valid, completely parenthesized, infix arithmetic expressions consisting of nonnegative integer digits, and the two operations +, -. The following definition gives all such valid expressions:
1. Any nonnegative integer is a valid infix expression.
2. If a and b are valid infix expressions, then (a+b), and (a-b) are valid infix expressions.
3. The only valid infix expressions are those defined by steps 1 and 2.
The character string ((5-1) +3) is an example of a complete parenthesized expression. All valid fully parenthesized infix expressions will have at least one operator.
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden..data
# myInputArray: .asciiz "Enter infix expression"
myInputArray: .asciiz "Expression to be evaluated:\n"
# outputArray: .asciiz "Result: "
# prompt_postfix: .asciiz "Postfix expression: "
# prompt_infix: .asciiz "Infix expression: "
infix: .align 2
postfix: .align 2
stack: .align 2
li $v0, 4
la $a0, myInputArray
# Get infix expression
li $v0, 8
la $a0, infix
la $a1, 256
# Convert to postfix
la $t1, infix # Get each Infix current byte address for each loop
la $t2, postfix
la $t3, stack
li $t0, 0 # infix iterator
li $t4, 0 # stack offset
add $t5, $t1, $t0 # set address of character
lb $t6, ($t5) # get character
beq $t6, '\n', emptyStack #check if end of infix expression
beq $t6, '(', openParenthesis # check if open parenthesis
beq $t6, ')', closedParenthesis # check if closed parenthesis
addi $a0, $t6, 0
jal isOperator # check if operator
beq $v0, 1, operator
addi $t6, $t6, -48 # it is an operand, get value from ASCII
sb $t6, ($t2) # put value in postfix expression
addi $t2, $t2, 1 # increment postfix iterator
addi $t0, $t0, 1 # increment infix iterator
# addi $t4, $t4, 1