以下笔记为jjyaoao本人制作，欢迎借鉴学习和提出相关建议，转载需要标明出处www.jjyaoao.space

4.栈

ADT接口

操作实例

实现

实际应用

进制转换

手动实现

难点

思路

算法实现

convert

void convert ( Stack<char>& S, __int64 n, int base ) { //整数n的1<base<=16进制打印（迭代版）
0002    char digit[] = "0123456789ABCDEF"; //数位符号，如有必要可相应扩充
0003    while ( n > 0 ) { //由低到高，逐一计算出新进制下的各数位
0004       S.push ( digit[ n % base ] ); //余数（当前位）入栈
0005       n /= base; //n更新为其对base的除商
0006    }
0007 } //新进制下由高到低的各数位，自顶而下保存于栈S中

括号匹配

问题描述

判断括号是匹配还是失配

尝试

构思

实现

bool paren ( const char exp[], int lo, int hi ) { //表达式括号匹配检查，可兼顾三种括号
0002    Stack<char> S; //使用栈记录已发现但尚未匹配的左括号
0003    for ( int i = lo; i <= hi; i++ ) /* 逐一检查当前字符 */
0004       switch ( exp[i] ) { //左括号直接进栈；右括号若与栈顶失配，则表达式必不匹配
0005          case '(': case '[': case '{': S.push ( exp[i] ); break;
0006          case ')': if ( ( S.empty() ) || ( '(' != S.pop() ) ) return false; break;
0007          case ']': if ( ( S.empty() ) || ( '[' != S.pop() ) ) return false; break;
0008          case '}': if ( ( S.empty() ) || ( '{' != S.pop() ) ) return false; break;
0009          default: break; //非括号字符一律忽略
0010    }
0011    return S.empty(); //最终栈空，当且仅当匹配
0012 }

反思

如果我们只考虑一个括号，又为什么不只用一个计数器来记录括号，而使用更加复杂的栈结构呢？

原因在于……

采用栈，可以更便捷的推广到多种括号并存的情况

教材与习题解析有这个的具体实现….

栈混洗

分别用尖括号和方括号来对应栈的顶部和底部

计数

对于长度为n的序列，栈混洗总数可能是多少呢？

A -> S S -> B他们所需的栈混洗次数其实是相互独立的

SP（1） = 1 （平凡情况）

甄别

+括号匹配

中缀表达式求值

构思

难点

栈+线性扫描

实现

readNumber

void readNumber ( char*& p, Stack<double>& stk ) { //将起始于p的子串解析为数值，并存入操作数栈
0002    stk.push ( ( double ) ( *p - '0' ) ); //当前数位对应的数值进栈
0003    while ( isdigit ( * ( ++p ) ) ) //若有后续数字（多位整数），则
0004       stk.push ( stk.pop() * 10 + ( *p - '0' ) ); //追加之（可能上溢）
0005    if ( '.' == *p ) { //若还有小数部分
0006       double fraction = 1; //则
0007       while ( isdigit ( * ( ++p ) ) ) //逐位
0008          stk.push ( stk.pop() + ( *p - '0' ) * ( fraction /= 10 ) ); //加入（可能下溢）
0009    }
0010 }

orderBetween

Operator optr2rank ( char op ) { //由运算符转译出编号
0002    switch ( op ) {
0003       case '+' : return ADD; //加
0004       case '-' : return SUB; //减
0005       case '*' : return MUL; //乘
0006       case '/' : return DIV; //除
0007       case '^' : return POW; //乘方
0008       case '!' : return FAC; //阶乘
0009       case '(' : return L_P; //左括号
0010       case ')' : return R_P; //右括号
0011       case '\0': return EOE; //起始符与终止符
0012       default  : exit ( -1 ); //未知运算符
0013    }
0014 }
0015 
0016 char priority ( char op1, char op2 ) //比较两个运算符之间的优先级
0017 { return pri[optr2rank ( op1 ) ][optr2rank ( op2 ) ]; }