08.stacks

  • May 2020
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View 08.stacks as PDF for free.

More details

  • Words: 3,174
  • Pages: 52
Bilgisayar Mühendisliği Bölümü

DATA STRUCTURES AND ALGORITHMS Lecture Notes 8 Stacks Spring 2008

GIT – Computer Engineering Department

ROAD MAP  The stack class and its member functions: – push, pop, top, empty, and size

 How the C++ standard library implements stack  How to implement stack using: – An array – A linked list

 Using stack in applications – Finding palindromes – Testing for balanced (properly nested) parentheses – Evaluating arithmetic expressions

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

2

The stack Abstract Data Type  A stack can be compared to a Pez dispenser – Only the top item can be accessed – Can only extract one item at a time

 A stack allows access only to the top element  A stack’s storage policy is Last-In, First-Out

Carl Barb

push Carl ...

Alex

GIT – Computer Engineering Department

Barb Alex

Simulation - Lecture Notes 7

3

The stack Abstract Data Type

top push Stack pop

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

4

Specification of Stack ADT Functions

Behavior

bool empty() const

Returns true if the stack is empty; otherwise returns false. Returns the object at the top of the stack without removing it. Removes the object at the top of the stack. Pushes the item onto the top of the stack. Returns the number of items in the stack.

Item_Type& top(); const Item_Type& top() const void pop() void push(const Item_Type& item) size_t size() const

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

5

Stack Applications  Text studies: two client programs using stacks – Palindrome finder – Parenthesis (bracket) matcher

 A palindrome is a string that is the same in either direction – “Able was I ere I saw Elba” – “A man, a plan, a canal: Panama” – Abba

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

6

Stack Applications (continued) Data Fields

Attributes

string input_string stack char_stack

The input string. The stack where characters are stored. Behavior Initializes a new Palindrome_Finder object, storing a copy of the parameter str in input_string and pushing each character onto the stack. Fills the stack with the characters in input_string. Returns the string formed by popping each character from the stack and joining the characters. Empties the stack. Returns true if input_string and the string build by build_reverse have the same contents, except for case. Otherwise, returns false.

Functions Palindrome_Finder(const string& str)

void fill_stack() string build_reverse()

bool is_palindrome()

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

7

Palindrome Code class Palindrome_Finder { public: Palindrome_Finder(const std::string& str): input_string(str) { fill_stack(); } bool is_palindrome(); private: void fill_stack(); std::string build_reverse(); std::string input_string; std::stack char_stack; };

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

8

Palindrome Code (2) /** Function to fill a stack of characters from an input string. */ void Palindrome_Finder::fill_stack() { for (size_t i = 0; i < input_string.size(); i++) { char_stack.push(input_string[i]); } }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

9

Palindrome Code (3) /** Builds a string containing the characters in a stack. post: The stack is empty. @return The string containing the words in the stack */ string Palindrome_Finder::build_reverse() { string result; while (!char_stack.empty()) { // Remove top item from stack and append it to result. result += char_stack.top(); char_stack.pop(); } return result; }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

10

Palindrome Code (4) /** Function class to perform case-insensitive comparison of characters. */ class Ci_Equal { public: bool operator()(char c1, char c2) { return toupper(c1) == toupper(c2); } };

bool Palindrome_Finder::is_palindrome() { string reverse = build_reverse(); return equal(input_string.begin(), input_string.end(), reverse.begin(), Ci_Equal()); }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

11

Testing Palindrome Finder  Single character, empty string: both always palindromes  Multiple characters, one word  Multiple words  Different cases (upper/lower)  Both even- and odd-length strings

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

12

Stack Applications: Balancing Brackets  Arithmetic expressions should balance parentheses: (a+b*(c/(d-e)))+(d/e)

 Not too hard if limited to parentheses only: – Increment depth counter on ( – Decrement depth counter on ) – If always ≥ 0, then balanced properly

 Problem harder if also use brackets: [] {} – A stack provides a good solution!

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

13

Balancing Brackets: Overview    

Start with empty stack of currently open brackets Process each char of an expression string If it is an opener, push it on the stack If it is a closer, check it against the top stack element – If stack empty, or not a matching bracket: not balanced, so return false – Otherwise, it matches: pop the opener

 If stack is empty at the end, return true  If not empty, then some bracket unmatched: false

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

14

is_balanced Code bool is_balanced(const string& expression) { // A stack for the open parentheses that haven't been matched stack s; bool balanced = true; string::const_iterator iter = expression.begin(); while (balanced && (iter != expression.end())) { char next_ch = *iter; if (is_open(next_ch)) { s.push(next_ch); } else if (is_close(next_ch)) { if (s.empty()) { balanced = false; } else { char top_ch = s.top(); s.pop(); balanced = OPEN.find(top_ch) == CLOSE.find(next_ch); } } ++iter; } return balanced && s.empty(); } GIT – Computer Engineering Department

Simulation - Lecture Notes 7

15

is_balanced Code: Helper Routines // The set of opening parentheses. const string OPEN = "([{"; // The corresponding set of closing parentheses. const string CLOSE = ")]}"; bool is_open(char ch) { return OPEN.find(ch) != string::npos; } bool is_close(char ch) { return CLOSE.find(ch) != string::npos; }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

16

Testing is_balanced     

Expressions without brackets Expressions with just one level Expressions with multiple levels, same kind Expressions with multiple levels, different kinds Expressions with same # open/close, but bad order: – )(

 Expressions with open/close order ok, wrong bracket: – (]

 Expressions with too many openers  Expressions with too many closers GIT – Computer Engineering Department

Simulation - Lecture Notes 7

17

Application: Function Calls – When a function is called • Local variables and status should be saved

– When the function returns • Saved values needs to be stored

– In what order?

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

18

Implementing stack an adapter of vector  The standard library implements the stack as an adapter of any sequential container.  The member functions are delegated to the member functions of the container.  Any of the three sequential containers can be used: vector, list, or deque.  The standard library uses the deque by default.  We will use the vector, and describe the deque in the next chapter.

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

19

Implementing Stack as Extension of Vector (2)

Top element of the Stack is at the highest index

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

20

stack Code template void stack::push(const Item_Type& item) { container.push_back(item); } template Item_Type& stack::top() { return container.back(); } template const Item_Type& stack::top() const { return container.back(); }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

21

Stack Code (2) template void stack::pop() { container.pop_back(); } template bool stack::empty() const { return container.empty(); } template size_t stack::size() const { return container.size(); }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

22

Implementing stack as a Linked Structure

 We can implement Stack using a linked list:

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

23

Linked_Stack Code template class stack { M private: // Data fields // Insert definition of class Node here #include "Node.h" /** A pointer to the top of the stack. */ Node* top_of_stack; }; // End class stack

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

24

Linked_Stack Code (2) template void stack::push(const Item_Type& item) { top_of_stack = new Node(item, top_of_stack); } template Item_Type& stack::top() { return top_of_stack->data; } template const Item_Type& stack::top() const { return top_of_stack->data; }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

25

Linked_Stack Code (3) template void stack::pop() { Node* old_top = top_of_stack; top_of_stack = top_of_stack->next; delete old_top; } template bool stack::empty() const { return top_of_stack == NULL; }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

26

Comparison of stack Implementations  The code for the vector version is very similar to the implementation in the C++ standard library.  By using delegation, we avoid having to implement the operations ourselves and are assured of O(1) performance.  Using the standard containers has a space penalty. – vector allocates additional space to provide amortized constant insertion time. – list uses a double linked list which has unneeded pointers.  Using a single linked list allocates space for the links, but these are necessary.  Using a single linked list also provides O(1) performance.

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

27

Additional Stack Applications: Evaluating Arithmetic Expressions

 Expressions normally written in infix form – Binary operators appear between their operands: a+b

c*d

e*f-g

 A computer normally scans in input order – One must always compute operand values first – So easier to evaluate in postfix form: ab+

cd*

ef*g-

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

28

Postfix Expression Evaluation Examples Postfix Expression

GIT – Computer Engineering Department

Infix Expression

Value

4 * 7

28

4 * (7 + 2)

36

(4 * 7) - 20

8

3 + ((4 * 7) / 2)

17

Simulation - Lecture Notes 7

29

Advantages of Postfix Form  No need to use parentheses for grouping  No need to use precedence rules: – Usual meaning of a + b * c is a + (b * c) – * takes precedence over + ... or ... – * has higher precedence than + – Postfix: a b c * + – For (a+b)*c, postfix is: a b + c *

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

30

Program: Evaluating Postfix Expressions  Input: string with integers and operators separated by spaces (for istream extraction)  Operators: + - * / (all binary, usual meaning)  Strategy: – Use stack for input integers, evaluated operands – Operator pops operands, computes, pushes result – At end, last item on stack is the answer

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

31

Algorithm for eval 1. Empty the operand stack 2. while there are more tokens 3. Get the next token 4. if the first character of the token is a digit 5. Push the integer onto the stack 6. else if the token is an operator 7. Pop the right operand off the stack 8. Pop the left operand off the stack 9. Evaluate the operation 10. Push the result onto the stack 11. Pop the stack and return the result GIT – Computer Engineering Department

Simulation - Lecture Notes 7

32

Program: Evaluating Postfix Expressions (3) Expression

Action

Stack

4 7 * 20 

Push 4

4 7 * 20 

Push 7

4 7 * 20 

Pop 7 and 4 Evaluate 4 * 7 Push 28 Push 20

┃ 4┃ ┃┃┃┃ ┃ 7┃ ┃ 4┃ ┃┃┃┃ ┃28┃ ┃┃┃┃

4 7 * 20  4 7 * 20  4 7 * 20 

GIT – Computer Engineering Department

Pop 20 and 28 Evaluate 28 - 20 Push 8 Pop 8 Stack is empty Result is 8 Simulation - Lecture Notes 7

┃20┃ ┃28┃ ┃┃┃┃ ┃ 8┃ ┃┃┃┃ ┃ ┃ ┃┃┃┃

33

Program: Evaluating Postfix Expressions (4) class Syntax_Error : public std::invalid_argument { public: Syntax_Error(std::string msg) : std::invalid_argument(msg) {} }; const std::string Postfix_Evaluator::OPERATORS = "+-*/";

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

34

Program: Evaluating Postfix Expressions (5) int Postfix_Evaluator::eval_op(char op) { if (operand_stack.empty()) throw Syntax_Error("Stack is empty"); int rhs = operand_stack.top(); operand_stack.pop(); if (operand_stack.empty()) throw Syntax_Error("Stack is empty"); int lhs = operand_stack.top(); operand_stack.pop(); int result = 0; switch(op) { case '+' : result = lhs + rhs; break; case '-' : result = lhs - rhs; break; case '*' : result = lhs * rhs; break; case '/' : result = lhs / rhs; break; } return result; } GIT – Computer Engineering Department

Simulation - Lecture Notes 7

35

Program: Evaluating Postfix Expressions (6) bool is_operator(char ch) { return OPERATORS.find(ch) != std::string::npos; }

int Postfix_Evaluator::eval(const std::string& expression) { // Be sure the stack is empty while (!operand_stack.empty()) operand_stack.pop(); // Process each token istringstream tokens(expression); char next_char; . . . } GIT – Computer Engineering Department

Simulation - Lecture Notes 7

36

Program: Evaluating Postfix Expressions (7) while (tokens >> next_char) { . . . } if (!operand_stack.empty()) { int answer = operand_stack.top(); operand_stack.pop(); if (operand_stack.empty()) { return answer; } else { throw Syntax_Error("Stack should be empty"); } } else { throw Syntax_Error("Stack is empty"); }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

37

Program: Evaluating Postfix Expressions (8) // loop body: work done for each token if (isdigit(next_char)) { tokens.putback(next_char); int value; tokens >> value; operand_stack.push(value); } else if (is_operator(next_char)) { int result = eval_op(next_char); operand_stack.push(result); } else { throw Syntax_Error("Invalid character encountered"); } } GIT – Computer Engineering Department

Simulation - Lecture Notes 7

38

Converting Infix to Postfix  Need to handle precedence  Need to handle parentheses – First implementation handles only precedence

 Input: Infix with variables, integers, operators – (No parentheses for now)

 Output: Postfix form of same expression

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

39

Converting Infix to Postfix (2)  Analysis: – Operands are in same order in infix and postfix – Operators occur later in postfix

 Strategy: – Send operands straight to output – Send higher precedence operators first – If same precedence, send in left to right order – Hold pending operators on a stack GIT – Computer Engineering Department

Simulation - Lecture Notes 7

40

Converting from Infix to Postfix: Example Next Token

Action

w

Append w to postfix

5.1

/

sum *

Stack Effect on Postfix

┃ ┃ ┃┃┃┃ The stack is empty. ┃ -┃ Push - onto the stack. ┃┃┃┃ Append 5.1 to postfix. ┃ /┃ ┃ -┃ ┃┃┃┃ precedence(/) > precedence(-) ┃ /┃ Push / onto the stack. ┃ -┃ ┃┃┃┃ Append sum to postfix. ┃ -┃ ┃┃┃┃ precedence(*) == precedence(/) ┃ /┃ Pop / off the stack and append to ┃ -┃ postfix. ┃┃┃┃

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

w w w 5.1

w 5.1

w 5.1 sum w 5.1 sum /

41

Converting from Infix to Postfix: Example (2) Next Token

Action

Stack Effect on Postfix

*

precedence(*) > precedence(-) Push * onto the stack.

w 5.1 sum /

2

Append 2 to postfix.

End of input

Stack is not empty, Pop * off the stack and append to postfix. Stack is not empty, Pop - off the stack and append to postfix.

┃ -┃ ┃┃┃┃ ┃ *┃ ┃ -┃ ┃┃┃┃ ┃ -┃ ┃┃┃┃ ┃ ┃ ┃┃┃┃

w 5.1 sum / 2 * -

End of input

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

w 5.1 sum / 2

w 5.1 sum / 2 *

42

Converting Infix to Postfix: convert 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

Set postfix to an empty string Set operator stack to an empty stack while more tokens in infix string Get the next token if the token is an operand Append the token to postfix else if the token is an operator Call process_operator to handle it else Indicate a syntax error Pop remaining operators and add them to postfix

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

43

Converting Infix to Postfix: process_perator 1. while the stack is not empty & prec(new) ≤ prec(top) 2.

pop top off stack and append to postfix

3. push the new operator

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

44

Converting Infix to Postfix Data Field

Attribute

stack operator_stack string postfix

Stack of operators The postfix string being formed

Public Functions

Behavior

string convert(string infix)

Extracts and process each token in infix and returns the equivalent postfix string.

Private Functions

Behavior

void process_operator(char op)

Process operator op by updating operator_stack. Returns the precedence of operator op Returns true if ch is an operator symbol.

int precedence(char op) const bool is_operator(char ch) const

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

45

Infix_To_Postfix Code const string Infix_To_Postfix::OPERATORS = "+-*/"; const int Infix_To_Postfix::PRECEDENCE[] = { 1, 1, 2, 2 }; bool is_operator(char ch) { return OPERATORS.find(ch) != std::string::npos; } int precedence(char op) { return PRECEDENCE[OPERATORS.find(op)]; }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

46

Infix toPostfix: Code (2) string Infix_To_Postfix::convert(const string& expression) { postfix = ""; while (!operator_stack.empty()) operator_stack.pop(); istringstream infix_tokens(expression); string next_token; while(infix_tokens >> next_token) { if (isalnum(next_token[0])) { postfix += next_token; postfix += " "; } else if (is_operator(next_token[0])) { process_operator(next_token[0]); } else { throw Syntax_Error("Unexpected Character Encountered"); } } // End while . . .

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

47

Infix toPostfix: Code (3) // Pop any remaining operators and append them to postfix while (!operator_stack.empty()) { char op = operator_stack.top(); operator_stack.pop(); postfix += op; postfix += " "; } return postfix; }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

48

Infix toPostfix: Code (4) void Infix_To_Postfix::process_operator(char op) { if (operator_stack.empty()) { operator_stack.push(op); } else { if (precedence(op) > precedence(operator_stack.top())) { operator_stack.push(op); } else { // Pop all stacked operators with equal // or higher precedence than op. while (!operator_stack.empty() && (precedence(op) <= precedence(operator_stack.top()))) { postfix += operator_stack.top(); postfix += " "; operator_stack.pop(); } // assert: Operator stack is empty or current // operator precedence > top of stack operator // precedence; operator_stack.push(op); } } } GIT – Computer Engineering Department

Simulation - Lecture Notes 7

49

Infix_To_Postfix: Handling Parentheses const string Infix_To_Postfix::OPERATORS = "+-*/()"; const int Infix_To_Postfix::PRECEDENCE[] = {1,1,2,2,-1,-1};

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

50

Infix toPostfix: Handling Parentheses (2) void Infix_To_Postfix::process_operator(char op) { if (operator_stack.empty() || (op == '(')) { if (op == ')') throw Syntax_Error("Unmatched close parenthesis"); operator_stack.push(op); } else { if (precedence(op) > precedence(operator_stack.top())) { operator_stack.push(op); } else { while (!operator_stack.empty() && (operator_stack.top() != '(') && (precedence(op) <= precedence(operator_stack.top()))) { postfix += operator_stack.top(); postfix += " "; operator_stack.pop(); } . . .

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

51

Infix toPostfix: Handling Parentheses (2) if (op == ')') { if (!operator_stack.empty()&&(operator_stack.top()=='(')) { operator_stack.pop(); } else { throw Syntax_Error("Unmatched close parentheses"); } } else { operator_stack.push(op); }

} } }

GIT – Computer Engineering Department

Simulation - Lecture Notes 7

52