Chapter 3: Stack

Examples

Outline Concept Implementation of Stack Implementation of Stack Class Applications

Stack Last In First Out (LIFO) First In Last Out (FILO)

Terminology: Top & Bottom

Terminology: Empty Stack

Terminology: Push (入栈) Insert a node to the top

Terminology: pop (出栈) Delete the top node

Operations create(): create an empty stack push(x): push x into the top pop(): delete the top node and return its value top(): return the value of the top node isEmpty(): is the stack empty? yes: true; no: false

Outline Concept Implementation of the Stack Implementation by sequence list Implementation by linked list Implementation of the Stack Class Applications

Sequence List of Stack Node in the stack  Element of an array Top of the stack  End of the array Advantage: push() & pop() do not result in a lot of movements 用连续的空间存储栈中的结点，即数组 进栈和出栈总是在栈顶一端进行，不会引起类似顺序表中的大量数据的移动。用数组的后端表示栈顶。

create() Apply for a dynamic array Pointer: data = address of this dynamic array Capacity: maxSize = size of this dynamic array Indicator: top_p = -1 (elements are numbered from 0)

push(x) Push x into the stack top_p++ & array[top_p] = x (if array is not full)

pop() Remove the top node x = array[top_p] & top_p-- return x = an

top() Return the value of the top node x = array[top_p] return x = an

isEmpty() Check if the stack is empty if top_p == -1, return true; otherwise return false return true return false

Complexity All operations except push(): 𝑂 1 push(): on average 𝑂 1 , worst case 𝑂 𝑁 array is not full 但最坏情况在N次进栈操作中至多出现一次。如果把扩展数组规模所需的时间均摊到每个插入操作，每个插入只多了一个拷贝操作，因此从平均的意义上讲，插入运算还是常量的时间复杂度。这种分析方法称为均摊分析法。 array is full

Outline Concept Implementation of Stack Implementation of Stack Class Implementation by sequence list Implementation by linked list Implementation of Stack Class Applications

Linked List of the Stack Singly linked list without head node is enough All operations are carried out at the top only top_p points to the top node

create() Create an empty linked list The only operation: top_p = null No node is created since ‘head’ is not needed any more

push(x) Push a node with value = x into the stack p = new node D of node = x

push(x) Push a node with value = x into stack P of node = top_p

push(x) Push a node with value = x into stack top_p = p

pop() p = top_p

pop() top_p = top_p->next x = p->D

pop() delete p return x

top() & isEmpty() top(): return top_p->D isEmpty(): { if (top_p == null) return true; else return false; }

Complexity All operations: 𝑂 1 No a lot of pointer movements 同学的问题：为什么不让链表的表头做栈底？

Outline Concept Implementation of Stack Implementation of Stack Class Applications

Abstract Class of Stack template <class elemType> class stack { public: virtual bool isEmpty() const = 0; virtual void push(const elemType &x) = 0; virtual elemType pop() = 0; virtual elemType top() const = 0; virtual ~stack() {} };

Sequence Stack Class template <class elemType> class seqStack: public stack<elemType> { private: elemType *elem; //指向栈底(即数组)的指针 int top_p; int maxSize; void doubleSpace(); //在push操作使用 public: seqStack(int initSize = 10) {//构造函数分配栈的初始容量 elem = new elemType[initSize]; maxSize = initSize; top_p = -1; }

Sequence Stack Class ~seqStack() { delete [] elem; } //析构函数释放空间 bool isEmpty() const { return top_p == -1; } void push(const elemType &x) { if (top_p == maxSize - 1) doubleSpace(); //栈已满，扩容 elem[++top_p] = x; } elemType pop() { return elem[top_p--]; } elemType top() const { return elem[top_p]; } };

doubleSpace template <class elemType> void seqStack<elemType>::doubleSpace(){ elemType *tmp = elem; elem = new elemType[2 * maxSize]; for (int i = 0; i < maxSize; ++i) elem[i] = tmp[i]; maxSize *= 2; delete [] tmp; }

Linked Stack Class template <class elemType> class linkStack: public stack<elemType> { private: struct node { elemType data; node *next; node(const elemType &x, node *N = NULL) { data = x; next = N; } node() : next(NULL) {} ~node() {} }; node *elem; //指向栈顶的指针，即前面讲的top_p

Linked Stack Class public: linkStack() { elem = NULL; } //初始化一个链表栈 ~linkStack(); bool isEmpty() const { return elem == NULL; } void push(const elemType &x) { node *tmp = new node(x, elem); elem = tmp; } //无边界问题 elemType pop() { node *tmp = elem; elemType x = tmp->data; elem = elem->next; delete tmp; return x; } //无边界问题 elemType top() const { return elem->data; } }; 用板书解释push和pop，说明没有类似于一般链表的边界情况，即不需要head和tail等节点。

Destructor template <class elemType> linkStack<elemType>::~linkStack() { node *tmp; while (elem != NULL) { //注意释放空间 tmp = elem; elem = elem->next; delete tmp; }

Outline Concept Implementation of Stack Implementation of Stack Class Applications Non-recursive implementation of recursive function Symbol balance checking Computation

Recursive Function int factorial(n) { if (n==0) return 1; else return n*factorial(n-1); } 递归的本质是函数调用，而函数调用是通过栈实现的。因此，递归可以用栈消除。 n!=n(n-1)!=n[(n-1)(n-2)!]=… 拓展一下：递归在现实中的例子

Function Call Function call is realized by the stack void f1() { … r1: f2(); r2: …} void f2() { … t1: f3(); t2: …} void f3() { … …} 递归是一种特殊的函数调用，我们可以先看看一般的函数调用过程中内存的变化。

Function Call Function call is realized by the stack void f1() { … r1: f2(); r2: …} void f2() { … t1: f3(); t2: …} void f3() { … …} 保存第一层调用函数的数据

Function Call Function call is realized by the stack void f1() { … r1: f2(); r2: …} void f2() { … t1: f3(); t2: …} void f3() { … …} 保存第二层调用函数的数据，并执行第三层调用函数

Function Call Function call is realized by the stack void f1() { … r1: f2(); r2: …} void f2() { … t1: f3(); t2: …} void f3() { … …} 第三层函数返回后，先取出后保存的第二层调用函数的数据，并执行第二层调用函数

Function Call Function call is realized by the stack void f1() { … r1: f2(); r2: …} void f2() { … t1: f3(); t2: …} void f3() { … …} 第二层调用函数执行完之后，取出最先保存的第一层数据，并执行完第一层调用函数。因此，在整个过程中，最后保存的数据最先处理，最先保存的数据最后处理，这完全符合栈的过程。这些栈的维护和操作由编译器自动完成。

Recursive Function: Print 1234 void printInt(int num) { if (num<10) cout.put(num + ‘0’); else { printInt(num/10); //r cout.put(num % 10 +‘0’); //r1 } 递归是一种特殊的函数调用，是在一个函数中又调用了函数本身。 递归程序的本质是函数调用，而函数调用是要花费额外的时间和空间。 在系统内部，函数调用是用栈来实现，如果程序员可以自己控制这个栈，就可以消除递归调用。

Recursive Function: Print 1234 void printInt(int num) { if (num<10) cout.put(num + ‘0’); else { printInt(num/10); //r cout.put(num % 10 +‘0’); //r1 }

Recursive Function: Print 1234 void printInt(int num) { if (num<10) cout.put(num + ‘0’); else { printInt(num/10); //r cout.put(num % 10 +‘0’); //r1 }

Recursive Function: Print 1234 void printInt(int num) { if (num<10) cout.put(num + ‘0’); else { printInt(num/10); //r cout.put(num % 10 +‘0’); //r1 }

Recursive Function: Print 1234 void printInt(int num) { if (num<10) cout.put(num + ‘0’); else { printInt(num/10); //r cout.put(num % 10 +‘0’); //r1 } 1

Recursive Function: Print 1234 void printInt(int num) { if (num<10) cout.put(num + ‘0’); else { printInt(num/10); //r cout.put(num % 10 +‘0’); //r1 } 12

Recursive Function: Print 1234 void printInt(int num) { if (num<10) cout.put(num + ‘0’); else { printInt(num/10); //r cout.put(num % 10 +‘0’); //r1 } 123

Recursive Function: Print 1234 void printInt(int num) { if (num<10) cout.put(num + ‘0’); else { printInt(num/10); //r cout.put(num % 10 +‘0’); //r1 } 1234

Recursion Eliminated by Stack Drawback: additional time and memory restore parameters restore the state of function restore addresses of return points Recursion can be eliminated by the stack

Recursive Structure Print tens first, and then print ones L4 1 L3 12 1234 123 4 12 1 L1 L2 3 2 L3 L4 先打印十位，再打印个位。递归到最后，先打印1，回到倒数第二层后打印2，回到倒数第三层后打印3，回到最上面一层后打印4，完成任务

Example: Print a Decimal Number 1234 void PrintNum(int num) //把先要打印的数字放在栈顶 { linkStack <int> s; int tmp; s.push(num); while (!s.isEmpty()) { tmp=s.pop(); if (tmp>9) { //先打十位再个位 s.push(tmp%10); //把个位入栈 s.push(tmp/10); } //再把十位入栈 else cout.put (tmp+‘0’); } 设置一个栈，记录要做的工作，即将要打印的正整数。然后不断地从栈中获取任务，完成该任务，直到完成了所有的任务即栈为空。 先将整个数进栈，然后重复下列工作，将打印一个正整数的工作分解成两个子工作，将子工作放入栈中： 打印十位数以上的数字 打印个位数字

Example: Print a Decimal Number 1234 void PrintNum(int num) { linkStack <int> s; int tmp; s.push(num); while (!s.isEmpty()) { tmp=s.pop(); if (tmp>9) { s.push(tmp%10); s.push(tmp/10); } else cout.put (tmp+‘0’); } 设置一个栈，记录要做的工作，即将要打印的正整数。然后不断地从栈中获取任务，完成该任务，直到完成了所有的任务即栈为空。 先将整个数进栈，然后重复下列工作，将打印一个正整数的工作分解成两个子工作，将子工作放入栈中： 打印十位数以上的数字 打印个位数字

Example: Print a Decimal Number 1234 void PrintNum(int num) { linkStack <int> s; int tmp; s.push(num); while (!s.isEmpty()) { tmp=s.pop(); if (tmp>9) { s.push(tmp%10); s.push(tmp/10); } else cout.put (tmp+‘0’); } 设置一个栈，记录要做的工作，即将要打印的正整数。然后不断地从栈中获取任务，完成该任务，直到完成了所有的任务即栈为空。 先将整个数进栈，然后重复下列工作，将打印一个正整数的工作分解成两个子工作，将子工作放入栈中： 打印十位数以上的数字 打印个位数字

Example: Print a Decimal Number 1234 void PrintNum(int num) { linkStack <int> s; int tmp; s.push(num); while (!s.isEmpty()) { tmp=s.pop(); if (tmp>9) { s.push(tmp%10); s.push(tmp/10); } else cout.put (tmp+‘0’); } 设置一个栈，记录要做的工作，即将要打印的正整数。然后不断地从栈中获取任务，完成该任务，直到完成了所有的任务即栈为空。 先将整个数进栈，然后重复下列工作，将打印一个正整数的工作分解成两个子工作，将子工作放入栈中： 打印十位数以上的数字 打印个位数字

Example: Print a Decimal Number 1234 void PrintNum(int num) { linkStack <int> s; int tmp; s.push(num); while (!s.isEmpty()) { tmp=s.pop(); if (tmp>9) { s.push(tmp%10); s.push(tmp/10); } else cout.put (tmp+‘0’); } 设置一个栈，记录要做的工作，即将要打印的正整数。然后不断地从栈中获取任务，完成该任务，直到完成了所有的任务即栈为空。 先将整个数进栈，然后重复下列工作，将打印一个正整数的工作分解成两个子工作，将子工作放入栈中： 打印十位数以上的数字 打印个位数字 1

Example: Print a Decimal Number 1234 void PrintNum(int num) { linkStack <int> s; int tmp; s.push(num); while (!s.isEmpty()) { tmp=s.pop(); if (tmp>9) { s.push(tmp%10); s.push(tmp/10); } else cout.put (tmp+‘0’); } 设置一个栈，记录要做的工作，即将要打印的正整数。然后不断地从栈中获取任务，完成该任务，直到完成了所有的任务即栈为空。 先将整个数进栈，然后重复下列工作，将打印一个正整数的工作分解成两个子工作，将子工作放入栈中： 打印十位数以上的数字 打印个位数字 12

Example: Print a Decimal Number 1234 void PrintNum(int num) { linkStack <int> s; int tmp; s.push(num); while (!s.isEmpty()) { tmp=s.pop(); if (tmp>9) { s.push(tmp%10); s.push(tmp/10); } else cout.put (tmp+‘0’); } 设置一个栈，记录要做的工作，即将要打印的正整数。然后不断地从栈中获取任务，完成该任务，直到完成了所有的任务即栈为空。 先将整个数进栈，然后重复下列工作，将打印一个正整数的工作分解成两个子工作，将子工作放入栈中： 打印十位数以上的数字 打印个位数字 123

Example: Print a Decimal Number 1234 void PrintNum(int num) { linkStack <int> s; int tmp; s.push(num); while (!s.isEmpty()) { tmp=s.pop(); if (tmp>9) { s.push(tmp%10); s.push(tmp/10); } else cout.put (tmp+‘0’); } 设置一个栈，记录要做的工作，即将要打印的正整数。然后不断地从栈中获取任务，完成该任务，直到完成了所有的任务即栈为空。 先将整个数进栈，然后重复下列工作，将打印一个正整数的工作分解成两个子工作，将子工作放入栈中： 打印十位数以上的数字 打印个位数字 1234

Outline Concept Implementation of Stack Implementation of Stack Class Applications Non-recursive implementation of recursive function Symbol balance checking Computation

Brace Balance Check Important issue: check if brackets are balanced Example: for (i=0; i<5; i++) { …; } Legitimate: [], (), {}, [()], {[()]} Illegitimate: [), {], ({[ unmatch )]} 编译程序的任务之一，就是检查括号是否配对。如：括号( 、 [ 和 { 后面必须依次跟随相应的 }、] 及 )，“后面必须有”。 简单地用开括号和闭括号的数量是否相等来判断 开括号与闭括号是否配对是不行的。例如，符号 串[（）]是正确的，而符号串（ [ ）]是不正确的。因为当遇到）那样的闭括号时，它与最近遇到开括号匹配 那么这种情况用栈就比较合适。凡是碰到左括号就入栈，当碰到右括号时取出最后入栈的左括号进行对比（即出栈）。如果匹配则合法；否则不合法。

Balance Check Algorithm S1. create an empty stack S2. read a token (字符) t from the input file S3. If t is an opening bracket, push it into the stack S4. If t is a closing bracket, check the stack A. If the stack is empty  error //说明没有左括号与之匹配 B. otherwise, ch = pop() S5. If ch does not match the closing bracket  error //不匹配 S6. Read the next token from the input file - If the file is not empty, jump to S3 - Otherwise, jump to S7 S7. If the stack is not empty  error //栈中的左括号未匹配完 Otherwise, brackets are all balance 使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对(根据栈的定义，刚出栈的开括号必定是离当前比括号最近的) 1. 首先创建一个空栈。 2. 从源程序中读入符号。 3. 如果读入的符号是开符号，那末就将其进栈。 4. 如果读入的符号是一个闭符号但栈是空的，出错。 否则，将栈中的符号出栈。 5. 如果出栈的符号和和读入的闭符号不匹配，出错。 6. 继续从文件中读入下一个符号，非空则转向3，否则执行7。 7. 如果栈非空，报告出错，否则括号配对成功。

Example: (3+(5 – 2)*(6 + 4)/2) S1. create an empty stack 使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对

Example: (3+(5 – 2)*(6 + 4)/2) S2. read a token S3. the input token is an opening bracket ‘(’ Push ‘(’ into the stack 使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对

Example: (3 +(5 – 2)*(6 + 4)/2) S6. read the next token and the file is not empty Repeat S3-S6 until the input token is ‘(’ S3. Push ‘(’ into the stack 使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对

Example: (3 +(5 – 2)*(6 + 4)/2) S6. read the next token and the file is not empty Repeat S3-S6 until the input token is ‘)’ S4. ch = pop() = ‘(’  match! 使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对

Example: (3 +(5 – 2)*(6 + 4)/2) S6. read the next token and the file is not empty Repeat S3-S6 until the input token is ‘(’ S3. push ‘(’ into the stack 使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对

Example: (3 +(5 – 2)*(6 + 4)/2) S6. read the next token and the file is not empty Repeat S3-S6 until the input token is ‘)’ S4. ch = pop() = ‘)’  match! 使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对

Example: (3 +(5 – 2)*(6 + 4)/2) S6. read the next token and the file is not empty Repeat S3-S6 until the input token is ‘)’ S4. ch = pop() = ‘)’  match! 使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对

Other Details If implement the algorithm based on C/C++ source code, we have to Check balance for three kinds of brackets: {, [, ), if they are not in comments, string constants, or character constants example: //commnets… /*comments…*/ “{34eryT\” (password) ‘{’ Identify escape characters (转义字符) example: \”???...?{???\” } 如果对C++的源程序使用此算法，至少需要考虑三种括号：圆括号、方括号和花括号。 但有时又不需要考虑圆括号、花括号、方括是否匹配的问题。例如，当括号出现在注释、字符串常量、字符常量中时，就不需要考虑它的匹配问题。 在C++中有很多转义字符，因此在读入一个字符时，还必须考虑如何识别转义字符。

Balance Check Class: Balance Functions: Input: file name of a source file checkBalance(): return number of errors error-line numbers 返回所有错误行号

Class Definition (cont’) class balance { public: balance(const char *s); int CheckBalance(); //检查是否平衡，否则返回错误行号 private: ifstream fin; //待检查文件 int currentLine; //正在检查的行号(传递括号的行号参数) int Errors; //已经发现的错误数 struct Symbol //记录文件中的符号及其行号 { char Token; int TheLine; }; //TheLine从currentLine处获取 enum CommentType { SlashSlash, SlashStar }; //‘//’和‘/*’ //注释

Class Definition bool CheckMatch(char Symb1, char Symb2, int Line1, int Line2); //具体实施两个符号匹配的检查 char GetNextSymbol(); //从文件中读入括号(忽略其它符号) void PutBackChar(char ch); //将读入的字符放回文件 void SkipComment(enum CommentType type); //跳过注释 void SkipQuote(char type); //跳过字符或字符串常量 char NextChar(); //从文件读入下一个符号 }; class noFile {}; //输入文件不存在时报错

constructor balance::balance(const char *s) { fin.open(s); //打开文件 if (!fin) throw noFile(); //文件空，报错 currentLine = 1; //设当前行号为1 Errors = 0; //初始化错误数为0 }

CheckBalance: Pseudo Code Initialize an empty stack: seqStack //S1用线性表做栈 while (lastChar = GetNextSymbol()) //S2读入下一个括号 switch (lastChar) //S6 {case ‘{’, ‘[’, ‘(’: push into the stack //S3开括号入栈 case ‘}’,‘]’,‘)’: //S4闭括号 if (the stack is empty) //S4-A检查栈是否为空 unmatched! Errors ++; else { match = pop(); //S4-B从栈中弹出一个括号 check if lastChar matches the match; //S5执行CheckMatch if unmatched, Errors++; } if (the stack is not empty) return these errors; //S7 return the errors; 检查输入流对象中的括号是否匹配，并返回错误数 算法的实现需要用到一个栈，我们可以用本章中实现的栈类，如seqStack。 采用逐步精细化的方法分解这个函数

CheckMatch bool balance::CheckMatch(char Symb1, char Symb2, int Line1, int Line2) { if (Symb1 == '(' && Symb2 != ')' || Symb1 == '[' && Symb2 != ']' || Symb1 == '{' && Symb2 != '}') cout << "发现第" << Line2 << "的符号" << Symb2 << "与第" << Line1 << "的符号" << Symb1 << "不匹配\n"; return false; } else return true;

GetNextSymbol Dig out a bracket from the input stream Ignore other symbols that are not bracket Ignore the brackets in the comments ‘/*…*/’ ‘//’ ‘\?’

GetNextSymbol: Pseudo Code Char GetNextSymbol() { while (ch = NextChar()) {//从文件中读入下一字符 if (ch == ‘/’) { //可能是注释的开始 ch = NextChar(); //再从文件中读入一个字符 if (ch == ‘*’) SkipComment(); //跳过标准C的注释 else if (ch == ‘/’) SkipComment(); //跳过C++的注释 else PutBackChar(); //非注释，把ch放回输入流供下次读取 } else if (ch == ‘\’||ch == ‘”’) SkipQuote(); //跳过字符常量 else if (ch == ‘{’|| ch == ‘[’|| ch == ‘(’|| ch == ‘)’|| ch == ‘]’||ch == ‘}’) return ch; //返回括号 return 0; //文件结束

Outline Concept Implementation of Stack Implementation of Stack Class Applications Non-recursive implementation of recursive function Symbol balance checking Computation

Infix Expression & Postfix Expression For expression a * (b – c * d) + e / f Infix (中缀) expression: a * (b – c * d) + e / f can not be understood by the computer Postfix (后缀) expression (reverse polish-style) a b c d * - * e f / + 后缀表达式是指将运算符放在运算数之后的表达式，不包含括号 后缀表达式是一种适合计算机理解的计算语义

Advantage of Postfix Expression Implicitly imply the priority of operators Example: a * (b – c * d) + e / f – infix a b c d * - * e f / + – postfix high priority low priority 后缀表达式隐含了各种计算的优先次序：把需要先计算的算符放到前面，后计算的在后面。

Calculation of Postfix Expression a b c d * - * e f / + a b A - * e f / + a B * e f / + C e f / + C D + 后缀表达式隐含了各种计算的优先次序：把需要先计算的算符放到前面，后计算的在后面。 从左往右扫描，遇到操作数不停，遇到操作符则让紧挨操作符的前面两个数进行计算，结果取代原来操作数和操作符的位置。这很像是栈的结构。

How does Postfix Express work? S1. Initialize a stack S2. Read the next token (t) S3. If t is an operand (操作数), push it to the stack S4. If t is an operator (操作符) //开始计算 - pop two operands on the top//当前操作数一定位于栈顶 - do (the second pop) t (the first pop) = (result) //注意顺序 - push the result into the stack //下一个操作符的操作数 S5. If the file is not empty, jump to S2 S6. If the file is empty & there is only one operand in the stack - pop it from the stack as the final result 1. 初始化一个栈。 2. 依次读入后缀式的操作数和运算符。 3. 若读到的是操作数，则将其进栈。 4. 若读到的是运算符，则将栈顶的两个操作数出 栈，后弹出的操作数为被操作数，先弹出的为操 作数，将得到的操作数完成运算符所规定的运算，并将结果进栈。 5. 回到2的读入操作，继续。 6. 当栈中只剩有一个操作数时，弹出该操作数，它就是表达式的值。

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S1. Initialize a stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S2. Read the next t S3. t = 5, push 5 into the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S5. File not empty, jump to S2 (read the next t) S3. t = 7, push 7 into the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S5. File not empty, jump to S2 (read the next t) S3. t = 2, push 2 into the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S5. File not empty, jump to S2 (read the next t) S3. t = 3, push 3 into the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S5. File not empty, jump to S2 (read the next t) S4. t = *, pop 3 & 2, push 2*3=6 to the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S5. File not empty, jump to S2 (read the next t) S4. t = -, pop 6 & 7, push 7-6=1 to the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S5. File not empty, jump to S2 (read the next t) S4. t is *, pop 1 & 5, push 5*1=5 to the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S5. File not empty, jump to S2 (read the next t) S3. t is 8, push 8 into the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S5. File not empty, jump to S2 (read the next t) S3. t is 2, push 2 into the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S5. File not empty, jump to S2 (read the next t) S4. t is /, pop 2 & 8, push 8/2=4 to the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S5. File not empty, jump to S2 (read the next t) S4. t = +, pop 4 & 5, push 5+4=9 to the stack

5 7 2 3 *-* 8 2 /+  5*(7-2*3)+8/2 S6. File is empty and there is only one operand 9 in the stack pop 9 as final result

Infix Expression vs. Postfix Expression a * (b – c * d) + e / f – infix a b c d * - * e f / + – postfix Relative location of the operands does not change Relative location of the operators changes 图示在后缀表达式中，操作数的顺序并没有改变，但是操作符的位置被调整了。因此问题是怎么决定中缀表达式中操作符的位置。

Transformation from Infix to Postfix a * (b – c * d) + e / f – infix * 为什么可以用栈来处理？ 图示在后缀表达式中，操作数的顺序并没有改变，只是操作符的顺序按照计算的优先级进行了调整。那么怎么决定中缀表达式中操作符的位置呢？ 遇到操作数直接可以输出，但是遇到操作符需要先保存起来。最后一个保存的操作符和新读入的操作符进行比较，然后根据优先级调整操作符的输出顺序。

Transformation from Infix to Postfix a * (b – c * d) + e / f – infix * - 为什么可以用栈来处理？ 图示在后缀表达式中，操作数的顺序并没有改变，只是操作符的顺序按照计算的优先级进行了调整。那么怎么决定中缀表达式中操作符的位置呢？ 遇到操作数直接可以输出，但是遇到操作符需要先保存起来。最后一个保存的操作符和新读入的操作符进行比较，然后根据优先级调整操作符的输出顺序。 √

Transformation from Infix to Postfix a * (b – c * d) + e / f – infix * - * 为什么可以用栈来处理？ 图示在后缀表达式中，操作数的顺序并没有改变，只是操作符的顺序按照计算的优先级进行了调整。那么怎么决定中缀表达式中操作符的位置呢？ 遇到操作数直接可以输出，但是遇到操作符需要先保存起来。最后一个保存的操作符和新读入的操作符进行比较，然后根据优先级调整操作符的输出顺序。 √

Transformation from Infix to Postfix a * (b – c * d) + e / f – infix * - * + 为什么可以用栈来处理？ 图示在后缀表达式中，操作数的顺序并没有改变，只是操作符的顺序按照计算的优先级进行了调整。那么怎么决定中缀表达式中操作符的位置呢？ 遇到操作数直接可以输出，但是遇到操作符需要先保存起来。最后一个保存的操作符和新读入的操作符进行比较，然后根据优先级调整操作符的输出顺序。 √

Transformation from Infix to Postfix a * (b – c * d) + e / f – infix * - + 为什么可以用栈来处理？ 图示在后缀表达式中，操作数的顺序并没有改变，只是操作符的顺序按照计算的优先级进行了调整。那么怎么决定中缀表达式中操作符的位置呢？ 遇到操作数直接可以输出，但是遇到操作符需要先保存起来。最后一个保存的操作符和新读入的操作符进行比较，然后根据优先级调整操作符的输出顺序。 √ *

Transformation from Infix to Postfix a * (b – c * d) + e / f – infix * + 为什么可以用栈来处理？ 图示在后缀表达式中，操作数的顺序并没有改变，只是操作符的顺序按照计算的优先级进行了调整。那么怎么决定中缀表达式中操作符的位置呢？ 遇到操作数直接可以输出，但是遇到操作符需要先保存起来。最后一个保存的操作符和新读入的操作符进行比较，然后根据优先级调整操作符的输出顺序。 √ * -

Transformation from Infix to Postfix a * (b – c * d) + e / f – infix + 为什么可以用栈来处理？ 图示在后缀表达式中，操作数的顺序并没有改变，只是操作符的顺序按照计算的优先级进行了调整。那么怎么决定中缀表达式中操作符的位置呢？ 遇到操作数直接可以输出，但是遇到操作符需要先保存起来。最后一个保存的操作符和新读入的操作符进行比较，然后根据优先级调整操作符的输出顺序。 * - *

Transformation from Infix to Postfix a * (b – c * d) + e / f – infix + / 为什么可以用栈来处理？ 图示在后缀表达式中，操作数的顺序并没有改变，只是操作符的顺序按照计算的优先级进行了调整。那么怎么决定中缀表达式中操作符的位置呢？ 遇到操作数直接可以输出，但是遇到操作符需要先保存起来。最后一个保存的操作符和新读入的操作符进行比较，然后根据优先级调整操作符的输出顺序。 √ * - *

Transformation from Infix to Postfix a * (b – c * d) + e / f – infix + 为什么可以用栈来处理？ 图示在后缀表达式中，操作数的顺序并没有改变，只是操作符的顺序按照计算的优先级进行了调整。那么怎么决定中缀表达式中操作符的位置呢？ 遇到操作数直接可以输出，但是遇到操作符需要先保存起来。最后一个保存的操作符和新读入的操作符进行比较，然后根据优先级调整操作符的输出顺序。 √ * - * /

Transformation from Infix to Postfix a * (b – c * d) + e / f – infix a b c d * - * e f / + – postfix 总是把最后一个保存的操作符和新读入的操作符进行比较，然后根据优先级调整操作符的输出顺序。 * - * / +

Algorithm: Infix  Postfix Initialize a stack //每次输出的一定是位于栈顶的操作符 S1. If t is an operand, output t //遇到操作数直接输出 S2. If t is an opening bracket, push it into the stack S3. If t is a closing bracket //出栈直至开括号,并生成子表达式 A. pop the operators in turn B. put the operators behind the operands C. stop pop if an opening bracket is popped S4. If t is an operator //栈顶高优先级操作符依次出栈，t入栈 A. if the operator on the top has a higher priority, pop this operator B. do A until all high-priority operators are popped C. push operator t into the stack S5. If the ‘read’ operation does not end, jump to S1; otherwise, do A. pop all operators in the stack 若读入的是操作数，立即输出。 若读入的是闭括号，则将栈中的运算符依次出栈， 并将其放在操作数序列之后。出栈操作一直进行到遇到相应的开括号为止。将开括号出栈。 若读入的是开括号，则进栈。 若读入的是运算符，如果栈顶运算符优先级高，则栈顶运算符出栈；出栈操作一直要进行到栈顶运算符优先级低为止，然后将新读入的运算符进栈保存。 在读入操作结束时，将栈中所有的剩余运算符依次出栈，并放在操作数序列之后，直至栈空为止。

Example: (5+6*(7+3)/3)/4+5 Initialize a stack

Example: (5+6*(7+3)/3)/4+5 S3. t = (

Example: (5+6*(7+3)/3)/4+5 S1. t = 5, output 5

Example: (5+6*(7+3)/3)/4+5 S4. t = +, push + into the stack as the top is (, which is not an operator with higher priority ‘(’不是高优先级运算符

Example: (5+6*(7+3)/3)/4+5 S1. t = 6, output 6

Example: (5+6*(7+3)/3)/4+5 S4. t = *, push * into the stack since ‘+’ < ‘*’

Example: (5+6*(7+3)/3)/4+5 S3. t = (, push ( into the stack

Example: (5+6*(7+3)/3)/4+5 S1. t = 7, output 7

Example: (5+6*(7+3)/3)/4+5 S4. t = +, push + into the stack as the top is (

Example: (5+6*(7+3)/3)/4+5 S1. t = 3, output 3

Example: (5+6*(7+3)/3)/4+5 S2. t = ), pop + & (, and put + behind 5673

Example: (5+6*(7+3)/3)/4+5 S4. t = /, push / into the stack since ‘*’ = ‘/’

Example: (5+6*(7+3)/3)/4+5 S1. t = 3, output 3

Example: (5+6*(7+3)/3)/4+5 S2. t = ), pop /,*,+,(, and put /,*,+ behind 5673+3

Example: (5+6*(7+3)/3)/4+5 S4. t = /, push / into the stack

Example: (5+6*(7+3)/3)/4+5 S1. t = 4, output 4

Example: (5+6*(7+3)/3)/4+5 S4. t = +, pop / since ‘/’ > ‘+’ and put / after 4 push + into the stack

Example: (5+6*(7+3)/3)/4+5 S1. t = 5, output 5

Example: (5+6*(7+3)/3)/4+5 S6. file reading operation ends, pop + and put + after 5

Another Example a * b / c * (e + f) – g a b c e f + * / * g – ?

a * b / c * (e + f) – g: Solution? a b c e f + * / * g – a b c A * / * g – a b B / * g – ? b / (c * (e + f))

a * b / c * (e + f) – g: Solution a b * c / e f + * g – A c / e f + * g – B e f + * g – B C * g – D g –

An Efficient Calculation It is possible to do calculation during the transformation from the Infix to the Postfix 做表达式转换的时候，我们用一个栈专门处理括号和操作符；作后缀表达式计算时，也用了一个处理操作数栈。是否可以让这两个栈相互配合，让转换和计算同时进行呢？ 后缀表达式计算过程，数据栈每次出栈的两个数，恰好是符号栈出栈的运算符的两个操作数。在中缀表达式中，这个两个数离操作符最近。 opStack dataStack

Example: (5+6*(7+3)/3)/4+5 Initialize stacks: opStack and dataStack

Example: (5+6*(7+3)/3)/4+5 t = (, push ( to opStack opStack dataStack

Example: (5+6*(7+3)/3)/4+5 t = 5, push 5 to dataStack opStack

Example: (5+6*(7+3)/3)/4+5 t = +, the top of opStack is (, thus push + to opStack opStack dataStack

Example: (5+6*(7+3)/3)/4+5 t = 6, push 6 to dataStack opStack

Example: (5+6*(7+3)/3)/4+5 t = *, opStack has no * / or ^, thus push * to opStack opStack dataStack

Example: (5+6*(7+3)/3)/4+5 t = 7, push 7 to dataStack opStack

Example: (5+6*(7+3)/3)/4+5 t = +, the top of opStack is (, thus push + to opStack opStack dataStack

Example: (5+6*(7+3)/3)/4+5 t = 3, push 3 to dataStack opStack

Example: (5+6*(7+3)/3)/4+5 t = ), BinaryOp(+,dataStack) opStack

Example: (5+6*(7+3)/3)/4+5 t = /, BinaryOp(*,dataStack), push / to opStack opStack dataStack

Example: (5+6*(7+3)/3)/4+5 t = 3, push 3 to opStack opStack dataStack

Example: (5+6*(7+3)/3)/4+5 t = ), BinaryOp(/,dataStack) opStack dataStack

Example: (5+6*(7+3)/3)/4+5 t = /, push / into opStack opStack dataStack

Example: (5+6*(7+3)/3)/4+5 t = 4, push 4 into dataStack opStack

Example: (5+6*(7+3)/3)/4+5 t = +, BinaryOp(/,dataStack), push + into opStack opStack dataStack

Example: (5+6*(7+3)/3)/4+5 t = 5, push 5 into opStack opStack dataStack

Example: (5+6*(7+3)/3)/4+5 We reach the end of the expression, do BinaryOp(+,dataStack), return 11.25 opStack dataStack

Implementation of a Calculator Input: an infix expression Operands (integers) +, - , *, /, ^ ( ) Output: result

Calculator Expression translation and calculation are carried out at the same time Two stacks are used Stack 1: store operators Stack 2: store operands 对前面的中缀转后缀程序稍微修改一下就可以实现边读入边计算

Definition of calc Class class calc{ private: char *expression; //保存输入的中缀表达式 enum token { OPAREN, ADD, SUB, MULTI, DIV, EXP, CPAREN, VALUE, EOL }; //字符常量 void BinaryOp(token op, seqStack<int> &dataStack); //从操作数栈中取操作数运算，并将结果放回操作数栈 token getOp(int &value); //从表达式中取字符 public: calc(char *s) //获取表达式字符串 { expression = new char[strlen(s) + 1]; strcpy(expression, s); } ~calc() { delete expression; } int result(); //计算表达式 };

result(): Pseudo Code int calc::result() { getOp(); //从表达式中取出一个符号，直到表达式结束 switch(current token t) { case VALUE: push t to the dataStack //将数字存入运算数栈 case ‘(’: push t to the opStack //开括号进运算符栈 case ‘)’: 开括号和闭括号之间的所有运算都可进行，即将 opStack中的运算符出栈进行运算，直到‘(’出栈 case ‘^’: 乘方运算符入运算符栈 case ‘*’: case ‘/’: opStack中的/, *, ^出栈执行，当前运算符 入栈 case ‘+’: case ‘-’: opStack中的运算符依次出栈执行，直到 栈为空或遇到开括号(+-的优先级最低)； 当前运算符进栈 }

result(): Pseudo Code 运算符栈中所有的运算符出栈执行 if (dataStack is empty) 出错，无运算结果 result_value = 运算数栈出栈元素 //出栈后运算数栈应为空 if (dataStack is not empty) 出错，缺运算符 运算结束之后，栈中应该有且只有一个数值 return result_value; } 倒数第三行：此次出栈后运算数栈应为空 假如非空，则有错，因为说明运算数栈剩下了两个元素，而此时运算符栈已空了。

BinaryOp() void calc::BinaryOp(token op, seqStack<int> &dataStack) { int num1, num2; //从数据栈中取数 if (dataStack.isEmpty()) { cerr << "缺操作数! "; exit(1); } else num2 = dataStack.pop(); else num1 = dataStack.pop(); //后弹出的放前面 switch(op) {//计算：操作符是result传递过来的 case ADD: dataStack.push(num1 + num2); break; case SUB: dataStack.push(num1 - num2); break; case MULTI: dataStack.push(num1 * num2); break; case DIV: dataStack.push(num1 / num2); break; case EXP: dataStack.push(pow(num1, num2)); } }

getOp() (cont’) calc::token calc::getOp(int &value) { while (*expression) { while(*expression && *expression == ' ') ++expression; //去掉空格 if (*expression <= ‘9’ && *expression >= ‘0’) //是数的开始 { value = 0; //初始化取值变量 while (*expression >='0' && *expression <='9') { value = value * 10 + *expression - ‘0’; //取出高位 ++expression; //指针移向低位 } //如遇到235时，先读出2，然后20+3，然后再230+5 return VALUE; //通过返回说明取到字符串的是数值型 } 如何取数？例如表达式为235+321。遇到235时，先读出百位2，然后20+3，然后再230+5。

getOp() //如果前面的if不成立，那么它是操作符 switch (*expression){ case '(': ++expression; return OPAREN; case ')': ++expression; return CPAREN; case '+': ++expression; return ADD; case '-': ++expression; return SUB; case '*': ++expression; return MULTI; case '/': ++expression; return DIV; case '^': ++expression; return EXP; } return EOL;

Homework 5, 6