栈的应用笔记

栈的应用

括号匹配算法：

//括号匹配
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxSize 10

bool bracketCheck(char str[],int length){
    //栈
    char a[MaxSize];
    int top;

    //初始化栈
    top=0;

    //扫描括号数组
    for(int i=0;i<length;i++){
        //如果是左括号，压入栈顶
        if(str[i]=='(' ||str[i]=='[' ||str[i]=='{'){
            a[top++]=str[i];
        }else{
            //是右括号，判断栈是否为空，为空则不符合要求
            if(top==0){
                return false;
            }else{
                //栈不为空，判断是否匹配
                //弹出栈顶元素
                if(a[top-1]=='('&&str[i]!=')'){
                    return false;
                }
                if(a[top-1]=='['&&str[i]!=']'){
                    return false;
                }
                if(a[top-1]=='{'&&str[i]!='}'){
                    return false;
                }
                top--;          //因为若这些都不符合则说明匹配成功，出栈

            }
        }
    }

    //扫描完成，若栈是空，则成功
    if(top!=0){
        return false;
    }
    return true;
}


int main(int argc,char *argv[]){
    char str[MaxSize]={'(','(','[',']','[',']',')',')'};
    printf("%d ",strlen(str));
    if(bracketCheck(str,strlen(str))){
        printf("Yes!\n");
    }else{
        printf("No!\n");
    }
    return 0;
}

中缀转后缀表达式计算

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符

从左到右依次处理各个元素，直到末尾，可能遇到三种情况

1.遇到操作数，直接加入后缀表达式

2.遇到界限符。遇到’('直接入栈；遇到’)‘则依次弹出栈内运算符并加入后缀表达式，直到弹出’('为止。注意：（不加入后缀表达式

3.遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到（或栈空则停止，之后再把当前运算符入栈

中缀表达式的计算（用栈实现）

中缀转后缀+后缀计算

初始化两个栈，操作数栈和运算数栈

若扫描到操作数，压入操作数栈

若扫描到运算符或者界限符（期间也会弹出运算符，每当弹出一个运算符时，就需要在弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再押回操作数栈）

栈在递归中的应用

函数调用时，需要用一个栈存储

1、调用返回地址

2、实参

3、局部变量