Sign InNuggetsCoursesCodePadCheatsheet

Postfix Evaluation

In most programming languages, mathematical expressions are written with the operator between the two operands, as in 1 + 2. This format is called infix. An alternative used by some calculators is called postfix. In postfix, the operator follows the operands, as in 1 2 +.

The reason postfix is sometimes useful is that there is a natural way to evaluate a postfix expression using a stack:

  1. Starting at the beginning of the expression, get one term (operator or operand) at a time.
  2. If the term is an operand, push it on the stack.
  3. If the term is an operator, pop two operands off the stack, perform the operation on them, and push the result back on the stack.
  4. When you get to the end of the expression, there should be exactly one operand left on the stack. That operand is the result.

In this task, you may assume the postfix expression is a string of tokens delimited by spaces. The operators are *, /, +, and - and the operands are assumed to be single-digit integer values. The output will be an integer result. To see this in more detail, consider the postfix expression 4 5 6 * +.

postfix evaluation example
class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[len(self.items)-1] def isEmpty(self): return (self.items == []) def eval_postfix(postfix_expr): operand_stack = Stack() token_list = postfix_expr.split() for token in token_list: if token in "0123456789": #TODO: push token to operand_stack as an integer else: #TODO: pop operand2 #TODO: pop operand1 result = calculate(token, operand1, operand2) #TODO: push result to operand_stack #TODO: pop result from operand_stack and return it def calculate(op, op1, op2): if op == "*": return op1 * op2 elif op == "/": return op1 / op2 elif op == "+": return op1 + op2 else: return op1 - op2 print(eval_postfix("5 1 - 3 2 + *"))
© CS Wonders·Home·About·Contact·Classes·Gallery·Glossary·Fun Facts