栈的应用

栈在括号匹配中的应用
如果遇到左括号则入栈，遇到右括号则弹出栈检测是否与左括号匹配

失败情况
1.左括号单身
2.右括号单身
3.左右括号不匹配

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


//初始化栈
void InitStack(SqStack &S)

//判断栈空 
bool StackEmpty(SqStack S)

//新元素入栈
bool Push(SqStack &S,char x)

//栈顶元素出栈
bool Pop(SqStack &S,char &x)



bool bracketCheck(char str[],int length)
{ 
    SqStack S;
    InitStack(&S);
    for(int i=0;i<length;i++)
    {
        if(str[i] == '('||str[i] == '['||str[i] == '}')
         Push(&S,str[i]);  // 扫描到左括号 入栈 
        else 
        {
            if(StackEmpty(S))
             return false ;
        char topchar;
        Pop(&S,&topchar); //栈顶元素出栈 
        if(str[i] == '(' && topchar != ')')
           return false ;
        if(str[i] == '[' && topchar != ')')
           return false ;
        if(str[i] == '{' && topchar != '}')
            return false;
                  }

          } 
      return StackEmpty(S);         //检验完所有括号，栈空说明匹配成功 
}

2.栈在表达式求值中的应用
（1.中缀表达式转后缀表达式
先初始化一个栈用于保存暂时还不能确定运算顺序的运算符，从左到右处理各个元素，
直到末尾，可能遇见三种情况：
a.遇到操作数，直接加入后缀表达式
b.遇到界限符。遇到（ 直接入栈 直到遇到） 在此过程中依次弹出栈内的运算符并加
入后缀表达式直到弹出（为止。注意（）不加入后缀表达式。
c.遇到运算符，依次弹出栈中的优先级高于或等于当前运算符的所有运算符，并加入后
缀表达式。

（2.后缀表达式的计算
a.从左往右扫描下一个元素，直到处理完所有元素
b.若扫描到操作数则压入栈。
c.若扫描到运算符，则弹出两个栈顶元素，执行响应运算，运算结果压入栈

（3.中缀表达式的计算
a.初始化两个栈，操作栈和运算符栈
b.若扫描到操作栈，压入操作数栈
c. 若扫描到运算符和界限符，则按照中缀转后缀相同的逻辑压入运算符栈
如果弹出运算符，每当弹出一个运算符，就需要弹出两个栈顶元素执行响应
运算，运算结果再压回操作数栈。