C Contemporary Abstract Al Homework. pd Course: Algorithms & Data ab-stack-infix
ID: 3795372 • Letter: C
Question
C Contemporary Abstract Al Homework. pd Course: Algorithms & Data ab-stack-infix-pdl C O ilearn capital.edu/pluginfile.php/620609/mod resource/content/O/cs1 ab-stack-in fix-pd CS161 Lab A Spring 2017 Infix to Postfix Due Thursday 02/23/2017 at 11:59PM Use the Stack.py file from the book Create a file named inToPost.py that implements the infix to post algorithm described in the book. The function must be named inToPost and take one parameter that is a string representing the infix expression. As you process the numbers in the string, convert them all to a floating point value. The function must return a string representing the corresponding postfix expression. Also write a function named evalPostfix that evaluates the resulting postfix expression (using the Stack class as described in the book) and returns a floating point value. Your main function must ask you to input an infix expression and call the inToPost function. Output the resulting postfix expression. Call the evalPostfix function with with the postfix expression and output the result of it (the answer to the original problem). You may not call the Python eval function. You may assume that each token in the infix expression is separated by a space. The following expression is an example of this: U3 +LAU)Uxu10utu4U*U5. This will allow you to use the string split method to break the string into separate tokens to process. When you create your postfix expression, also put spaces between each token to make it easier to process. I suggest you append each token to a list and then turn that into a string using the statement oin (e) where e is the list of items in the postfix expression For 5 bonus points, modify your code so that the expression does not require spaces separating each token in the infix expression. Two possible techniques are to write a function that processes the expression a character at a time and adds spaces creating a new string that can be sent to the existing function. The other technique is to directly process the expression a character at a time and determines where one token stops and the next one starts. You may want to append digits of a number to a list and then create the number when a non-digit is reached. Write a unit test that tests your inToPost and evalPoBtfix functions. Name the unit test file test MikeExplanation / Answer
def tokenize(expression):
tokenList = []
currentToken = ''
for character in expression:
if (character in ['(',')','+','-','*','/']):
if(len(currentToken)!=0):
tokenList.append(currentToken)
currentToken = ''
tokenList.append(character)
else:
currentToken += character
if(len(currentToken) != 0):
tokenList.append(currentToken)
return tokenList
def inToPost(expression):
tokenList = tokenize(expression)
postfixExp = []
precendenceOrder = {}
precendenceOrder['('] = 0
precendenceOrder['*'] = 2
precendenceOrder['/'] = 2
precendenceOrder['+'] = 1
precendenceOrder['-'] = 1
#Since the stack.py mentioned in the question is not provided, Using the python list as a stack
opStack = []
for token in tokenList:
if (token == '('):
opStack.append(token)
elif (token == ')'):
while(opStack[-1] != '('):
postfixExp.append(opStack.pop())
opStack.pop()
elif (token in ['+','-','/','*']):
while((len(opStack) != 0) and (precendenceOrder[opStack[-1]] >= precendenceOrder[token])):
postfixExp.append(opStack.pop())
opStack.append(token)
else:
postfixExp.append(token)
while(len(opStack) != 0):
postfixExp.append(opStack.pop())
return ' '.join(postfixExp)
def operate(operator, operand1, operand2):
if(operator == '+'):
return str(float(operand1) + float(operand2))
elif(operator == '-'):
return str(float(operand1) - float(operand2))
elif(operator == '*'):
return str(float(operand1) * float(operand2))
elif(operator == '/'):
return str(float(operand1) / float(operand2))
def evalPostfixExpression(expression):
postfixTokens = expression.split(' ')
print postfixTokens
stack = []
for token in postfixTokens:
if(token in ['+','-','/','*']):
operand2 = stack.pop()
operand1 = stack.pop()
stack.append(operate(token, operand1, operand2))
else:
stack.append(token)
return stack.pop()
exp = inToPost('(46565/((88)+3225))*(5/66)')
answer = evalPostfixExpression(exp)
print answer
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.