4.2 栈应用

逆序输出 conversion
输出次序与处理过程相反，递归深度与输出长度不易预知
递归嵌套 stack permutation + parenthesis
具有自相似性的问题可递归描述，但分支位置与嵌套深度不固定
延迟缓冲 evaluation
线性扫描算法模式中，在预读足够长度后，方能确定可处理的前缀
栈式计算 RPN
基于栈结构的特定计算模式

进制转换

void convert(Stack<char> & S, __int64 n, int base) {
    static char digit[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
    while (n > 0) { // 由低到高，逐一计算目标进制的各数位
        S.push(digit[n % base]); // 余数（对应数位）入栈
        n /= base; // n更新为其对base的除商
    }
}

main() {
    Stack<char> S;
    convert(S, n, base); // 使用栈记录转换所得各数位
    while (!S.empty())
        printf("%c", S.pop()); // 逆序输出
}

括号匹配

bool paren(const char exp[], int lo, int hi) { // exp[lo, hi)
    Stack<char> S; // 使用栈记录已发现但尚未匹配的左括号
    for (int i = lo; i < hi; i++) // 逐一检查当前字符
        if ('(' == exp[i])
            S.push(exp[i]); // 遇左括号，入栈
        else if (!S.empty())
            S.pop(); // 遇右括号，若栈非空，则弹出左括号
        else
            return false; // 否则必不匹配
    return S.empty(); // 最终当且仅当栈空时匹配
}

栈混洗
栈A = <a₁, a₂, ..., a_n]、B = S = Ø，只允许将A的顶元素弹出并压入S，或将S的顶元素弹出并压入B，若经一系列上述操作后，A中元素全部转入B中，B = [a_k1, a_k2, ..., a_kn>，则称为A的一个栈混洗(stack permutation)
同一输入序列，可有多种栈混洗
对于长度为n的序列，可能的栈混洗数

任意3个元素能否按某相对次序出现于混洗中，与其它元素无关
对于任意1 <= i < j < k <= n，[..., k, ..., i, ..., j, ...>必非栈混洗，称为禁形
O(n)判定算法：直接借助栈A、B与S，模拟混洗过程，每次S.pop()前检测S是否已空，或需弹出元素在S中却非顶元素
每一栈混洗，对应于栈S的n次push与n次pop操作构成的序列

中缀表达式

float evaluate(char* S, char* & RPN) { // 中缀表达式求值
    Stack<float> opnd; // 运算数栈
    Stack<char> optr; // 运算符栈
    optr.push('\0'); // 尾哨兵'\0'作为头哨兵首先入栈
    while (!optr.empty()) { // 逐个处理字符，直至运算符栈空
        if (isdigit(*S)) // 若当前字符为操作数
            readNumber(S, opnd); // 则读入（可能多位）操作数
        else // 若当前字符为运算符，则视其与栈顶运算符间优先级高低
            switch(orderBetween(optr.top(), *S)) { /* 分别处理 */ }
    }
    return opnd.pop(); // 弹出并返回计算结果
}

const char pri[N_OPTR][N_OPTR] = { // 运算符优先级[栈顶][当前]
//       +    -    *    /    ^    !    (    )    \0
/* + */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* - */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* * */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* / */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* ^ */ '>', '>', '>', '>', '>', '>', '<', '>', '>',
/* ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>',
/* ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ',
/* ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
/* \0 */'<', '<', '<', '<', '<', '<', '<', ' ', '=',
};

switch(orderBetween(optr.top(), *S)){ // 不同优先级处理方法
    case '<': // 栈顶运算符优先级更低
        optr.push(*S);
        S++;
        break; // 计算推迟，当前运算符进栈
    case '=': // 优先级相等（当前运算符为右括号或尾部哨兵'\0'）
        optr.pop();
        S++;
        break; // 脱括号并接收下一个字符
    case '>': // 栈顶运算符优先级更高，实施相应计算，结果入栈
        char op = optr.pop(); // 栈顶运算符出栈，执行对应运算
        if ('!' == op)
            opnd.push(calcu(op, opnd.pop())); // 一元运算符
        else {
            float pOpnd2 = opnd.pop();
            float pOpnd1 = opnd.pop(); // 二元运算符
            opnd.push(calcu(pOpnd1, op, pOpnd2)); // 实施计算，结果入栈
        }
        break;
}

逆波兰表达式(Reverse Polish Notation, RPN)
在由运算符(operator)与操作数(operand)组成的表达式中不使用括号(parenthesis-free)，即可表示带优先级的运算关系

float evaluate(char* S, char* & RPN) { // RPN转换
    while (!optr.empty()) { // 逐个处理字符，直至运算符栈空
        if (isdigit(*S)) { // 若当前字符为操作数
            readNumber(S, opnd);
            append(RPN, opnd.top()); // 则直接将其接入RPN
        } else { // 若当前字符为运算符
            switch(orderBetween(optr.top(), *S)) {
                case '>': // 且可立即执行
                    char op = optr.pop();
                    append(RPN, op); // 则在执行相应计算的同时将其接入RPN
            }
        }
    }
}