QuestionQuestion

Objective
To acquire expertise in stack manipulation and management, subroutine linkage and return conventions, and recursive procedures.

Description
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.

Example
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:

Console
Expression to be evaluated:
((1 - 3) + 5)
13-5+ = 3

Postfix Notation

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.

Solution PreviewSolution Preview

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
.space 256
postfix: .align 2
.space 256
stack: .align 2
.space 256
.text
main:
li $v0, 4
la $a0, myInputArray
syscall
# Get infix expression
li $v0, 8
la $a0, infix
la $a1, 256
syscall

# 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

loopInfix:
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
j loopInfix...
$50.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Computer Science - Other Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats