QuestionQuestion

Transcribed TextTranscribed Text

A Stack Machine to Evaluate Expressions Purpose: Implement and use a Stack ADT to convert infix mathematical expressions to postfix, and then evaluate the postfix expressions. Input will be from a text file, and output will be written to a file. Stack ADT (stack.py) You will implement a Stack ADT (class Stack) that supports the following operations: push(item): push an item onto the stack. Size increases by 1. popl: remove the top item from the stack and return it. Raise an IndexError if the stack is empty. top(): return the item on top of the stack without removing it. Raise an IndexError if the stack is empty. size():return the number of items on the stack. clear() : empty the stack. Pseudocode For Main Program (main.py) Pseudocode for main program: 1. open file data.txt 2. read an infix expression from the file 3. display the infix expression 4. call function in2post(expr) which you write in2post[ takes an infix expression as an input and returns an equivalent postfix expression as a string. If the expression is not valid, raise a SyntaxError. If the parameter expr is not a string, raise a ValueError. 5. display the postfix expression 6. call function eval_postfix(expr) which you write eval_postfix() takes a postfix string as input and returns a number. If the expression is not valid, raise a SyntaxError 7. display the result of eval_postfix() Output must match the format shown in Figure 1 below. Program Output infix: 4 postfix: 4 answer: 4.0 infix: 5 +7 postfix: 5 7 + answer: 12.0 infix: 7*5 postfix: 75 * answer: 35.0 infix: (5-3) postfix: 5 3 - answer: 2.0 infix: 5/5 postfix: 5 5 / answer: 1.0 infix: 8*5+3 postfix: 8 5 * 3 + answer: 43.0 infix: 8*(5+3) postfix: 8 5 3 + * answer: 64.0 infix: 8+3*5-7 postfix: 8 3 5 * + 7 - answer: 16.0 infix: (8+3)*(5-6) postfix: 83+56- - * answer: -11.0 infix: ((8+3)*(2-7)) postfix: 83+27 - * answer: -55.0 infix: ( 8+3)*2)-7 postfix: 83+2*7 - answer: 15.0 infix: (8*5)+((3-2)-7*3) postfix: 85*32- - 7 3 * - + answer: 20.0 infix: ((8*5+3)-7)-(5*3) postfix: 85*3+7- - 5 3 * - answer: 21.0 infix: 7*9+7-5*6+3-4 postfix: 79 * 7 + 5 6 * - 3 + 4 - answer: 39.0 Figure 1. Example Program Output A great explanation video for these following two algorithms is found at: https://www.youtube.com/watch?v=HJOnJU77EUs This has a C++ flavor, but can be very helpful to Python students as well. Evaluate a Postfix Expression 1. Initialize a stack 2. if next input is a number: Read the next input and push it onto the stack else: Read the next character, which is an operator symbol Use top and pop to get the two numbers off the top of the stack Combine these two numbers with the operation Push the result onto the stack 3. goto #2 while there is more of the expression to read 4. there should be one element on the stack, which is the result. Return this. Infix to Postfix Pseudocode 1. initialize stack to hold operation symbols and parenthesis 2. if the next input is a left parenthesis: Read the left parenthesis and push it onto the stack else if the next input is a number or operand Read the operand (or number) and write it to the output else if the next input is an operator: while (stack is not empty AND stack's top is not left parenthesis AND stack's top is an operation with equal or higher precedence than the next input symbol) : Print the stack's top Pop the stack's top Push the next operation symbol onto the stack else: Read and discard the next input symbol (should be a right parenthesis) Print the top operation and pop it while stack's top is not a left parenthesis: Print next symbol on stack and pop stack Pop and discard the last left parenthesis 3. Goto #2 while there is more of the expression to read 4. Print and pop any remaining operations on the stack There should be no remaining left parentheses Test Cases Following is the set of assertion-based test cases that your code must pass, and on which your grade for the project will be based. You will be given the pytest unit test code to run against your code as you develop it. This allows you to learn how test are written, and to know what your score is going to be when the code is graded before you submit it. NOTE: THIS IS A DRAFT SET OF TEST CASES, NOT READY FOR GRADING PURPOSES Test Empty Stack Create an empty Stack assert size is 0 assert pop raises IndexError Test Nominal Stack Create an empty Stack push 3 items onto the stack assert size is 3. test that pop returns the lastitem pushed but does not alter size. Verify that the data pushed is still on the stack and accessible with top and pop. verify that top and pop will both raise an IndexError when done on an empty stack. push 100 item onto stack and the use clear. Verify that the size after clear is zero. Test eval_postfix (expr) 14 different postfix expressions will be fed into eval_postfix() and the proper result will be tested. eval_postfix() will be fed an invalid post fix string and it must raise a SyntaxError. eval_postfix() will be fed a non-string as its parameter and it must raise a ValueError Test in 2post (expr) test 14 different in-fix equation and verify that the proper post fix an invalid infix expression is passed into in2post() and it should raise a SyntaxError a non-string will be passed into in 2post() and it should raise a ValueError Test program output Test that output if main() matches output as shown in Figure 1

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

from stack import Stack


def in2post(expr):
    precedence = {"^": 3, "*": 2, "/": 2, "+": 1, "-": 1}
    op_stack = Stack()
    output_list = []
    for token in expr:
       if token is None:
            raise ValueError()

       if token == '(':
            op_stack.push(token)
       elif token in "0123456789":
            output_list.append(token) # Read the operand (or number) and write it to the output
       elif token in precedence.keys():
            while not op_stack.is_empty() and \
                            op_stack.top() != "(" and \
                            precedence[op_stack.top()] >= precedence[token]:
                output_list.append(op_stack.pop())
            op_stack.push(token)
       else:
            if token == ")":
                if not op_stack.is_empty(): # and op_stack.top() != "(":
                   output_list.append(op_stack.pop())
                else:
                   raise SyntaxError()
                found_left = False
                while not op_stack.is_empty() and op_stack.top() != "(":
                   output_list.append(op_stack.pop())
                if not op_stack.is_empty() and op_stack.top() == "(":
                   found_left = True
                   op_stack.pop()
                if not found_left:
                   raise SyntaxError()
    while not op_stack.is_empty():
       if op_stack.top() != "(":
            output_list.append(op_stack.pop())
    if not op_stack.is_empty():
       raise SyntaxError()
    # print("".join(output_list))
    return "".join(output_list)...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

50% discount

Hours
Minutes
Seconds
$11.75 $5.88
for this solution

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

Find A Tutor

View available Data Structures and Algorithms 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