Question

Use python. DO NOT use pres existing libraries. Suppose there exists a text file called "expressions.txt". This file contains simple arithmetic expressions written in infix notation. Using the Stack class, write code to implement the Shunting Yard Algorithm to generate postfix expressions. Each expression in expressions.txt is written on a single line. Moreover, each expression contains only numbers comprising a single digit. Each token is separated by whitespace. Write each postfix expression generated to a file "answers.txt". Only consider the operations +, -, /, *, and ^.

Answer 1

Code screenshots:

Code to copy:

class Stack:
   def __init__(self):
       self.arr = []
   def push(self, item):
       self.arr.append(item)
   def pop(self):
       self.arr.pop()
   def peek(self):
       return self.arr[len(self.arr)-1]
   def isEmpty(self):
       return len(self.arr)==0

def Shunting_Yard_Algorithm(expr):
   st = Stack()
   res = ''
   #split the expression into tokens with respect to white space
   token_list = expr.split()
   #precedence dictionary
   precedence = {'(':0, '+':1, '-':1, '*':2, '/':2, '^':3}
   for token in token_list:
        #If digit then add to result
       if token.isdigit():
           res +=token+' '
       #If operator
       elif token in '()+-*/^':
           #If stack is empty then just push the token
           if st.isEmpty():
               st.push(token)
           #If toke is ( then just push (
           elif token=='(':
               st.push(token)
           #If token is ) then pop elements until we reach ( and add to res
           elif token==')':
               while st.peek()!='(':
                   res += st.peek()+' '
                   st.pop()
               #pop ( from stack
               st.pop()
           else:
                #Pop and add to result until we found top of stack is lower prior than current token
               while token != '^' and not st.isEmpty() and precedence[st.peek()]>=precedence[token]:
                   res +=st.peek()+' '
                   st.pop()
               #Push the token
               st.push(token)
   #Pop and add to result until stack is empty
   while not st.isEmpty():
       res +=st.peek()+' '
       st.pop()
   #return the result
   return res

#Open the file in read mode
file = open('expressions.txt','r')
#split into line by line
lines = file.read().split('\n')
postfix=''
#pass each line to algorithms add result to postfix
for expr in lines:
   postfix += Shunting_Yard_Algorithm(expr)+'\n'
#close the file
file.close()

#Open file in write mode
file = open('answers.txt','w')
#Write the postfix to file
file.write(postfix)
#close the file
file.close()

expressions.txt

1 + 2 * ( 3 + 4 )
1 * 2 + ( 3 / 4 )
1 - 2 + 3 * ( 4 - 5 * 6 )
1 - 2 + 3
1 * 2 - 3 ^ 4 + 5 / 6
1 * 2 - 3 ^ 4 * 5 / 6
1 ^ 2 ^ 3
1 ^ 2 ^ 3 * 4 / 5 * 6 - 7 * ( 8 + 9 )
( 1 + 2 ) ^ ( 3 - 4 ) * ( 5 * 6 ) / ( 7 / 8 ) + ( 9 ^ 1 )

answers.txt

1 2 3 4 + * +
1 2 * 3 4 / +
1 2 - 3 4 5 6 * - * +
1 2 - 3 +
1 2 * 3 4 ^ - 5 6 / +
1 2 * 3 4 ^ 5 * 6 / -
1 2 3 ^ ^
1 2 3 ^ ^ 4 * 5 / 6 * 7 8 9 + * -
1 2 + 3 4 - ^ 5 6 * * 7 8 / / 9 1 ^ +