本文共 3970 字，大约阅读时间需要 13 分钟。

Stack 模板类：

#include "Vector.h"template 
   
    class Stack : public Vector
    
      {    public:        void push ( T const& e) {insert(size(), e);}        T pop() {return remove(size() - 1);}        T& top() {return (*this) [size() - 1];}};
    
   

栈结构的应用：

1. 逆序输出

例如：进制转换

void convert(Stack
   
     & 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;    }}
   

2. 递归嵌套

例如：

括号匹配：

bool paren (const char exp[], int lo, int hi){    Stack
   
     S;    for ( int i = lo; i <= hi; i++)        switch(exp[i]){            case '(': case '[':case '{': S.push(exp[i]); break;            case ')': if ((S.empty())||('(' != S.pop())) return false; break;            case ']': if ((S.empty())||('[' != S.pop())) return false; break;            case '}': if ((S.empty())||('{' != S.pop())) return false; break;            default : break;        }    return S.empty();}
   

3. 延迟缓冲

表达式求值：

运算符优先级表：

#define N_OPTR 9 //运算符总数typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator; //运算符集合//加、减、乘、除、乘方、阶乘、左括号、右括号、起始符与终止符 const char pri[N_OPTR][N_OPTR] = { //运算符优先等级 [栈顶] [当前]/*              |-------------------- 当 前 运 算 符 --------------------| *//*              +      -      *      /      ^      !      (      )      \0 *//* --  + */    '>',   '>',   '<',   '<',   '<',   '<',   '<',   '>',   '>',/* |   - */    '>',   '>',   '<',   '<',   '<',   '<',   '<',   '>',   '>',/* 栈  * */    '>',   '>',   '>',   '>',   '<',   '<',   '<',   '>',   '>',/* 顶  / */    '>',   '>',   '>',   '>',   '<',   '<',   '<',   '>',   '>',/* 运  ^ */    '>',   '>',   '>',   '>',   '>',   '<',   '<',   '>',   '>',/* 算  ! */    '>',   '>',   '>',   '>',   '>',   '>',   ' ',   '>',   '>',/* 符  ( */    '<',   '<',   '<',   '<',   '<',   '<',   '<',   '=',   ' ',/* |   ) */    ' ',   ' ',   ' ',   ' ',   ' ',   ' ',   ' ',   ' ',   ' ',/* -- \0 */    '<',   '<',   '<',   '<',   '<',   '<',   '<',   ' ',   '='};

优先级判定：

void readNumber(char*& p, Stack
   
    & stk){    stk.push((float)(*p - '0'));    while(isdigit(*(++p)))        stk.push(stk.pop()*10+(*p - '0'));    if ('.' != *p) return;    float fraction = 1;    while(isdigit(*(++p)))        stk.push(stk.pop()+(*p -'0')*(fraction/=10));}Operator optr2rank (char op){    switch (op)    {    case '+': return ADD;        break;    case '-': return SUB;        break;    case '*' : return MUL;        break;    case '/': return DIV;        break;    case '^': return POW;        break;    case '!': return FAC;        break;    case '(': return L_P;        break;    case ')': return R_P;        break;    case '\0': return EOE;        break;        default:        break;    }}char orderBetween( char op1,char op2){    return pri[optr2rank(op1)][optr2rank(op2)];}
   

中缀表达式求值： 

float evaluate( char* S, char* RPN){    Stack
   
     opnd; Stack
    
      optr;    optr.push('\0');    while( !optr.empty()){        if(isdigit(*S))            readNumber(S, opnd);        else             switch(orderBetween(optr.top(), *S)){                case '<':                    optr.push(*S); S++;                    break;                case '=':                    optr.pop(); S++;                    break;                case '>':                    char op = optr.pop(); append(RPN, op);                    if ('!' == op) {                        float p0pnd = opnd.pop();                        opnd.push( calcu(op, p0pnd));                    }else {                        float p0pnd2 = opnd.pop(), p0pnd1 = opnd.pop();                        opnd.push( calcu(p0pnd1, op, p0pnd2));                    }                break;                default: exit(-1);            }    }    return opnd.pop();}
    
   

void append(char*& rpn, char optr){    int n = strlen(rpn);    rpn = (char*)realloc(rpn, sizeof(char)*(n+3));    sprintf(rpn+n, "%c", optr); rpn[n + 2] = '\0';}

栈混洗

逆波兰表达式：RPN

4. 栈式计算