Property: LIFO, FILO
Operation: push_front, pop_front
stk.add(obj)
stk.remove(&obj)
------
STL style
stk.push(obj);
stk.pop();
obj = stk.top();
Implement with dynamic array
must_have:
maxsize, // avoid overflow
array, // pointer to the dynamic array storage
top; // top of the stack
Implement with link list
must_have:
top; // top of the stack
Stack applications
syntax balancing check
function call
math expression evaluation
Math Expression
what is infix, prefix, postfix
why?
reverse polish notation (postfix)
convert infix to postfix
example: a+b*c+(d*e+f)*g
algorithm:
operand => output
operator => pop until lower priority, then push
( => push
) => pop until corresponding left parentheses
What's a better data structure for finding operator priority?
explore STL map if you're up to it
expression evaluation (from postfix)
example: abc*+de*f+g*+
algorithm:
operand => push
operator => pop operand(s), eval, push result
What IF: operand is floating point
What IF: operator is multiple characters, e.g. mod, div, ++, **
What IF: new operator is added
Tree representation of math expression
inorder traversal
preorder traversal
postorder traversal