Expression Evaluation Using Stacks - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: Expression Evaluation Using Stacks (/thread-25893.html) |
Expression Evaluation Using Stacks - walrus_overlord2 - Apr-15-2020 Hello, first time posting because this is the first assignment we have done that has me seriously stumped. The assignment is as follows: Write a python program to evaluate an arithmetic expression given by the user as a string of characters and prints the result of the expression. The solution follows a simple algorithm that uses two separate stacks: • A stack named operations which stores the operations from the expression. Operations are [+, −,∗] • Another stack named values to store the numbers from the expression. An expression consists of parentheses, operators, and the numbers (operands). Proceeding from left to right and taking these entities one at a time, you need to manipulate the stacks according to four possible cases, as follows: • Push the numbers onto the values stack. • Push the operators onto the operations stack. • Ignore left parentheses. • On encountering a right parenthesis: o Pop an operation from operations stack o Pop the requisite number of operands from values stack o Push onto the values stack the result of applying that operator to those operands. After the final right parenthesis has been processed, there will be one value left on the stack, which is the value of the expression. You return/print that value. Use the following example to test your program: Expression (keep spacing to work): ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Result should be 101 This is what I have: class Stack: def __init__(self): self.elements = [] def isEmpty(self): numberofElements = len(self.elements) if numberofElements == 0: return True else: return False def peek(self): if self.isEmpty(): return None else: return self.elements[len(self.elements)- 1] def push(self, value): self.elements.append(value) def pop(self): if self.isEmpty(): return None else: return self.elements.pop() def getSize(self): return len(self.elements) def importance(operator): if operator == '+' or operator == '-': return 1 if operator == '*' or '/': return 2 return 0 def applyoperation(a, b, op): if op == '+': return a + b if op == '-': return a - b if op == '*': return a * b if op == '/': return a // b def evaluate(spaces): values = [] operations = [] i = 0 #------------ Keeping track of 'while' separations'---------------# while i < len(spaces): if spaces[i] == ' ': i = i + 1 continue elif spaces[i] == '(': operations.append(spaces[i]) elif spaces[i].isdigit(): val = 0 while (i < len(spaces) and spaces[i].isdigit()): val = (val * 10) + int(spaces[i]) i = i + 1 values.append(val) elif space[i] == ')': while len(operations) != 0 and operations[-1] != '(': value2 = values.pop() value1 = values.pop() op = operations.pop() values.append(applyoperation(value1, value2, op)) operations.pop() else: while (len(operations) != 0 and importance(ops[-1]) >= importance(spaces[i])): value2 = values.pop() value1 = values.pop() op = operations.pop() values.append(applyoperation(value1, value2, op)) operations.append(spaces[i]) i = i + 1 #------------- Keeping track of 'while' separations'------------------------------------------------------------# while len(operations) != 0: value2 = values.pop() value1 = values.pop() op = operations.pop() values.append(applyoperations(value1, value2, op)) return values[-1] def main(): expression = input("Enter your expression of integers and operations separated by spaces: ") print() print(evaluate(expression)) main() This is what I get as an output: When I add a Stack in the main to use the evaluate function, this is what I get instead: Anybody have some pointers as to what I'm doing wrong? He sprung this on us quite suddenly and no previous assignments were seemingly so advanced. Any advice for how to modify this to work would help.
RE: Expression Evaluation Using Stacks - jefsummers - Apr-15-2020 Functions within a class should have self as the first argument in the function definition. In the posted code you do not create an instance of the class. You caught that, but each of the in class functions needs to have self as a paramenter RE: Expression Evaluation Using Stacks - walrus_overlord2 - Apr-15-2020 I fixed all the in-class functions to have self as the first parameter, and kept the instance of the class in the main, but there still seems to be an issue. This is the main function: def main(): mystack = Stack() expression = input("Enter your expression of integers and operations separated by spaces: ") mystack.push(expression) print() print(evaluate(mystack)) main()And this is the output The main issue now seems to be the in-class Evaluate function not working like it's meant to by returning the result of the expression.
RE: Expression Evaluation Using Stacks - jefsummers - Apr-15-2020 The interpreter does not know where to find the function evaluate. In line 6 of the posted code (probably line 101 or so in your real code) print(evaluate... needs to be print(mystack.evaluate(x))which brings up another issue. Not clear to me from your code what you call evaluate on - what is spaces? Is it supposed to be the input string? The way you have it, evaluate(mystack) would call evaluate on the entire class object, functions and all. You don't want to do that. Call mystack.evaluate() on the data you want evaluate() to act upon. |