stack

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

• 1. syntax balancing check

  2. function call

  3. 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