逆序输出 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 = <a1, a2, ..., an]、B = S = Ø，只允许将A的顶元素弹出并压入S，或将S的顶元素弹出并压入B，若经一系列上述操作后，A中元素全部转入B中，B = [ak1, ak2, ..., akn>，则称为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
}
}
}
}
网友评论