# Postfix Expressions

### From charlesreid1

## About

Postfix expressions:

- expressions in which the operation being specified occurs after the two operands, in a nested way

Example: each postfix expression evaluates to 9.

5 4 + 2 7 * 4 1 + - 1 1 + 1 1 + + 1 1 + 1 1 + + +

## Stacks

Postfix expressions can be evaluated by pushing the expressions onto a stack, where the stack deals with expressions. Expressions can consist of a single node (a number), or two expressions and an operator (making the expression definition recursive - like a tree).

In terms of stacks, we can push digits onto the stack UNTIL we reach a symbol, then apply the symbol to the next two expressions on the stack, turn the result into an expression, and push the result expression onto the stack.

## Trees

To represent a postfix expression with an expression tree, we can use a binary tree - particularly, we have to have a *proper* binary tree. (Each node can have zero or two children.)

We look at the whole expression one piece at a time, pushing the pieces onto the stack, until we reach an operator, whereupon we pop two elements off the stack, and apply the operator to them. The result becomes a new element, and gets pushed onto the stack.

# Flags

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |