Stack What is Stack? Definition A collection of elements that are inserted and removed according to the last-in first-out (LIFO) principle. The last element will be the first element to be removed. Input and output are only possible at the top on the stack. A B C D 2 What is Stack? Terminology Top: The top of stack (default = -1) Push: Insert an item on the top. Pop: Remove the item on the top. How does the stack work? 3 2 5 A top

7 top 2 2 5 5 5 5 Push 2 Push 3 Pop Push 7 top top 2 top Empty Push 5 3 top What is Stack? Operations

InitStack: Make stack empty. IsFull: Check whether stack is full. IsEmpty: Check whether stack is empty. Peek: Read the item at the top. Push: Insert an item at the top. Pop: Remove the item at the top. Q: Can we access items other than at the top? A: By definition, No. 7 2 5 4 top Array-based Implementation Stack representation items[ ] top -1 0 1 1 2 3 #define MAX_STACK 4 100

typedef enum { false, true } bool; typedef int Data; typedef struct { Data items[MAX_STACK]; int top; } Stack; 5 MAX_STACK- Array-based Implementation Operations // Make stack empty. void InitStack(Stack *pstack); // Check whether stack is full. bool IsFull(Stack *pstack); // check whether stack is empty. bool IsEmpty(Stack *pstack); // Read the item at the top. Data Peek(Stack *pstack); // Insert an item at the top. void Push(Stack *pstack, Data item); // Remove the item at the top. void Pop(Stack *pstack); 6 Array-based Implementation Initialize and IsFull operations // Make stack empty. void InitStack(Stack *pstack) { pstack->top = -1; } A top // Check whether stack is full. bool IsFull(Stack *pstack) {

return pstack->top == MAX_STACK 1; } 7 8 7 2 5 top Array-based Implementation IsEmpty and Peek operations // check whether stack is empty bool IsEmpty(Stack *pstack) { return pstack->top == -1; } A top // Read the item at the top. Data Peek(Stack *pstack) { if (IsEmpty(pstack)) exit(1); //error: empty stack return pstack->items[pstack->top]; } 8 7 2 5 top Array-based Implementation Push operation // Insert an item at the top.

void Push(Stack *pstack, Data item) { if (IsFull(pstack)) exit(1); //error: stack full pstack->items[++(pstack->top)] = item; } 7 3 2 5 top top 3 2 2 5 5 Push 3 Push 7 9 top Array-based Implementation Pop operation // Remove the item at the top. void Pop(Stack *pstack) { if (IsEmpty(pstack)) exit(1); //error: empty stack --(pstack->top); }

7 top 3 3 2 2 2 5 5 5 Pop Pop top 10 top Print a Reverse String Print a string in the reverse order. E.g., abcd dcba How to do this with a stack? Push all characters into stack. Read the top, print it and pop until stack is empty. a

d d c c c c b b b b b b a a a a a a Push c Push d Peek, Print & Pop Peek, Print & Pop

Peek, Print & Pop Push a Push b 11 a Peek, Empty Print & Pop Print a Reverse String Implementation void ReversePrint(char* s, int len) { Stack stack; char ch; InitStack(&stack);// Make a stack empty. for (int i = 0; i < len; i++) // Push characters. Push(&stack, s[i]); while (!IsEmpty(&stack))// Pop characters. { ch = Peek(&stack); printf("%c", ch); Pop(&stack); } } 12 Parenthesis Matching Problem Check if each opening symbol has a corresponding closing symbol and the pairs of parentheses are nested properly. First open waits until last close (

( ) ( ( ) ) ( ) ) Most recent open matches first close Example Balanced: (()()()()), (((()))), (()((())())) Unbalanced: ((((((()), ())), (()()(() 13 Parenthesis Matching How to do this with a stack? Push all open symbols into stack. Whenever finding the close symbol, pop the open symbol. If the stack is empty, it is not balanced. After reading all parentheses, check the status of the stack. If the stack is empty, it is balanced. Otherwise, it is not balanced.

Example: ( ( ( ) ( ) ) ) ( ( Push ( ( ( ( ( ( ( ( ( ( ( ( ( Pop Push ( Pop Pop Push ( Push ( 14 Pop Empty

Parenthesis Matching Implementation bool IsParanBalanced(char* exp, int len) { Stack stack; InitStack(&stack); // Make a stack empty. for (int i = 0; i < len; i++) { if (exp[i] == '(') // Check open symbol Push(&stack, exp[i]); else if (exp[i] == ')') { // Check close symbol if (IsEmpty(&stack)) return false; // Unbalanced case else Pop(&stack); } } if (IsEmpty(&stack)) return true; // Balanced case else return false; // Unbalanced case } 15 Maze Solving Problem Find a path from the starting positon to the goal point position. At any moment, you can only move one step in one of four directions (up, down, left, and right). Representation The maze is represented by a 2D binary array.

0: path, 1: block Starting X X Goal 16 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 0 1 1

1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 Maze Solving How to do this with a stack? 1 2 3 4

0 2 3 5 3 4 5 (1, 2) (2, 1) Po 2) p ( 1 , , 4 4 3 4 3 2 3 2 1 2 Po 1) p ( 1

2 1 1 Push right direction. 1 5 5 5 (1, 1) 0 4 0 0 0 5 1 Push down and right direction. 17 , 0 (1, 3) (2, 1) Push right direction.

Po 3) p ( 1 Maze Solving How to do this with a stack? 2 3 4 0 2 3 0 4 5 0 0 0 5 1 4 , , 4 4 Po

4) p ( 1 5 3 3 3 Push down and right direction. 4 2 2 2 (1, 1) 3 1 1 1 (2, 3) 2 5 5 5 (1, 4) 1 (2, 3) (2, 1)

18 , 1 (3, 3) (2, 1) Push down direction. Po 3) p ( 3 0 Po 3) p ( 2 Maze Solving How to do this with a stack? 1 2 3 4 0 2 3 0 4 5

0 0 0 5 1 2 2 2 3 3 3 4 Push down and right direction. Po 4) p ( 3 , 4 4 (2, 1) 5 1 1 1 (4, 3)

2 5 5 5 (3, 4) 1 (3, 5) (4, 3) (2, 1) Push right direction. 19 , 0 Po 5) p ( 3 (4, 3) (2, 1) 3 4 Maze Solving Overall process 1. When extending the path, push a new position on the stack. 1.1. At the current position, extend the path one step by trying to go three directions (up, down, or right). 2. Pop a position to move the current position.

3. If none of the neighboring positions is available, pop a position on the stack. 3.1. If the stack is empty, it indicates failure. Repeat steps 1~3 until the goal has been reached. 20 Evaluation of Expression How to evaluate the expression? 3+4 *(5/2)+(7+9*3) Evaluation by human Assign to each operator a priority. Use parenthesis and evaluate inner-most ones. ((3+(4 *(5/2)))+(7+(9* 3))) How to evaluate by computer? How to evaluate the operators with parenthesis How to determine the precedence of operators 21 Infix, Postfix, and Prefix Infix notation: X + Y Postfix notation: X Y +

Operators are written after their operands. The order of evaluation of operators is always left-to-right. Unnecessary to use parenthesis and precedence of operators. Operators are written in-between their operands. Need extra information to make the order of evaluation of the operators clear. Prefix notation: + X Y Operators are written before their operands. As for postfix, operators are evaluated left-to-right. 22 Infix vs. Postfix Example Infix Postfix Prefix A*B+C/D AB * CD/ + + *AB / C D A * (B + C) / D AB C +* D/ / *A+ B C D

A * (B + C / D) AB C D/ +* *A+ B / C D A*B/CD AB*C/D- - / *AB C D Why is postfix useful? No parenthesis is needed No precedence of operators is needed 23 Converting Infix to Postfix Applying the conversion rule in a recursive way Operand_1 Operator Operand_2 Operand_1 Operand_2 Operator Example 4 3 - 5 * (4-3)*5 (4-3) 4 3 5 * 24 How to Evaluate Postfix Notation

Overall process 1. Push operands on the stack until finding an operator. 2. If the operator is found, pop two operands and evaluate the operator. Then, push the result on the stack. Repeat steps 1~2 until reading all characters in postfix notation. 25 How to Evaluate Postfix Notation Example: 2 3 4 * + Push operands on the stack until finding an operator. If the operator is found, pop two operands and evaluate the operator. Then, push the result on the stack. 234* + 234* + 234* + 234* + 234* + 4 3 3 12 2 2 2 2

14 Push 2 Push 3 Push 4 Pop Pop Pop Pop Eval: 3 * 4 Push 12 Eval: 2 + 12 Push 14 26 How to Evaluate Postfix Notation Example: 2 3 + 4 * Push operands on the stack until finding an operator. If the operator is found, pop two operands and evaluate the operator. Then, push the result on the stack. 23+ 4* 23+ 4* 23+ 4* 3

23+ 4* 23+ 4* 4 2 2 5 5 20 Push 2 Push 3 Pop Push 4 Pop Pop Pop Eval: 2 + 3 Push 5 Eval: 4 * 5 27 Push 20 How to Evaluate Postfix Notation int EvalPostfix(char* exp, int len) { Stack stack; int op1, op2;

InitStack(&stack); for (int i = 0; i < len; i++) { if (isdigit(exp[i])) // Push an operand. Push(&stack, exp[i] - '0'); else { // Evaluate an operator. op2 = Peek(&stack); Pop(&stack); op1 = Peek(&stack); Pop(&stack); if (exp[i] == '+') Push(&stack, op1 + op2); else if (exp[i] == '-') Push(&stack, op1 - op2); else if (exp[i] == '*') Push(&stack, op1 * op2); else if (exp[i] == '/') Push(&stack, op1 / op2); } } return Peek(&stack); } 28 Converting Infix to Postfix Overall process 1. If the operand is found, print it. 2. If the operator is found, push it into stack, but before pushing 2.1. See the operator at the top of the stack. 2.2. If the priority of the incoming operator is lower than or equal to the top, pop and print the top and go to step 2.1. Repeat steps 1~2 until reading all characters in infix notation. 3. At the end of the infix notation, pop all operators. 29 Converting Infix to Postfix Example: 2 + 3 * 4 While reading a character form infix notation

If we find operand, print it. Otherwise, check the priority of operator and determine whether push it into stack. Pop all operators at the end of the infix notation. 2+3* 4 Print 2 2 2+3* 4 2+3* 4 2+3* 4 2+3* 4 2+3* 4 * * * + + + + + Compare

the priority with top. Print 3 Compare the priority with top. Print 4 Pop all, and print them. Push + 23 Push * 30 234 234* + Converting Infix to Postfix Example: 2 * 3 + 4 While reading a character form infix notation If we find operand, print it. Otherwise, check the priority of operator and determine whether push it into stack. Pop all operators at the end of the infix notation.

2*3+ 4 Print 2 2 2*3+ 4 2*3+ 4 2*3+ 4 2*3+ 4 2*3+ 4 * * + + + Compare the priority with top. Print 3 Compare the priority with top. Pop * Print 4 Pop all, and print

them. Push * 23 Push + 31 23*4 23*4 + Converting Infix to Postfix Implementation void ConvInfixToPostfix(char* exp, char* convExp, int len) { Stack stack; int idx = 0; InitStack(&stack); for (int i = 0; i < len; i++) { if (isdigit(exp[i])) convExp[idx++] = exp[i]; // Print an operand. else { while (!IsEmpty(&stack) && ComPriority(Peek(&stack), exp[i])) { convExp[idx++] = Peek(&stack); // Print an operator. Pop(&stack); // Pop an operator. } Push(&stack, exp[i]); // Push an operator. } } while (!IsEmpty(&stack)) { convExp[idx++] = Peek(&stack); // Print an operator. Pop(&stack); // Pop an operator. } } 32 Converting Infix to Postfix

Implementation int GetPriority(char op) { if (op == '*' || op == '/') return 2; else if (op == '+' || op == '-') return 1; else return 0; } bool ComparePriority(char op1, char op2) { int op1_pr = GetPriority(op1); int op2_pr = GetPriority(op2); if (op1_pr >= op2_pr) return true; else return false; } 33