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