栈的应用（括号匹配、表达式求值、递归）

栈的应用1，括号匹配

遇到一个左括号就入栈，遇到有括号就消耗一个左括号

流程图如图

这里要用到栈这种数据结构，包括栈的初始化，判断栈是否为空，入栈和出栈操作，具体的可以看之前写的栈的c语言实现

#define MaxSize 10
 
typedef struct{
    char data[MaxSize];
    int top;
} SqStack;

void InitStack(SqStack &s){
    s.top=-1;
}

bool StackEmpty(SqStack &s){
    if (s.top==-1) {
        return true;
    }else{
        return false;
    }
}

bool Push(SqStack &s,char x){
    if (s.top==MaxSize-1) {
        return false;
    }
    s.top++;
    s.data[s.top]=x;
    return true;
}

bool Pop(SqStack &s,char &x){
    if (s.top==-1) {//top为-1，栈空
        return false;
    }
    
    x=s.data[s.top];
    s.top--;
    return true;
}

bool bracketCheck(char str[],int length){
    SqStack s;
    InitStack(s);//初始化一个栈
    for (int i=0; i 
 
 
栈在表达式求值中的运用
 
中缀转后缀的手算方法，按照左优先的原则
 
 
用栈实现后缀表达式的计算
 
1、从左往右扫描下一个元素
 
2、若扫描到操作数则压入栈，并返回1，否则执行3
 
3、若扫描到运算符，则弹出两个栈顶元素，并执行相应的运算，（先出栈的是右操作数，后出栈的是左操作数）运算结果压回栈顶，回到1
 
 
前缀表达式的计算
 
1、从右往左扫描下一个元素
 
2 3跟上面的一样，注意先出栈的是左操作数，后出栈的是右操作数
 
 
中缀表达式转后缀表达式的方法
 
从左到右处理各个元素，直到末尾，可能余姚三种情况
 
1 遇到操作数，直接加入后缀表达式
 
2遇到界限符，遇到（直接入栈，遇到）则依次弹出栈内运算符并加入后缀表达式，直到弹出（为止，注意：（不加入后缀表达式
 
3 遇到运算符，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到（或栈空则停止，之后再把当前运算符入栈
 
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式
 
 
中缀表达式的计算（用栈实现）
 
用栈实现中缀表达式的计算
 
初始化两个栈，操作数栈和运算符栈
 
若扫描到操作数，压入操作数栈
 
若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，则需要再弹出两个操作数栈顶元素并执行相应的运算，运算结果再次压入操作数栈
 
栈的应用——递归