栈的应用

WhYqZz2025-09-032025-09-23

括号匹配问题

分析

( ( ( ( ) ) ) )

最后的左括号最先被匹配(LIFO)——可以用栈实现这个特性

( ( ( ) ) ( ) )

每出现一个右括号，就消耗一个左括号(出栈)
遇到左括号就入栈，遇到右括号就消耗一个左括号，并且与右括号的大小进行比较

算法实现

代码

#define MAXSIZE 10
typedef struct{
    char data[MAXSIZE];
    int top;
}SqStack;
void InitStack(SqStack &S){
    S.top=0;
}
bool Push(SqStack &S,char x){
    S.data[S.top]=x;
    S.top++;
    return true;
}
bool Pop(SqStack &S,char &x){
    S.top--;
    x=S.data[S.top];
    return true;
}
bool StackEmpty(SqStack &S){
    if(S.top==0)return true;
    else return false;
}
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 TopElem;
            Pop(S,TopElem);
            if(str[i]==')'&&TopElem!='(')return false;
            if(str[i]==']'&&TopElem!='[')return false;
            if(str[i]=='}'&&TopElem!='{')return false;
        }
    }
    return StackEmpty(S);//检索完全部括号后，栈空说明匹配成功
}

表达式求值

逆波兰表达式==后缀表达式

波兰表达式==前缀表达式

中缀表达式：运算符在两个操作数中间

a+b
a+b-c
a+b-c*d
后缀表达式：运算符在两个操作数后边

ab+
ab+c-
ab+cd*-
前缀表达式：运算符在两个操作数前边 +ab -+abc

+ab
-+abc
-+ab*cd

中缀表达式转换为后缀表达式(手算)

确定中缀表达式中各个运算符的运算顺序
选择下一运算符，按照[左操作数右操作数运算符]的方式组合成一个新的操作数
如果还有运算符没被处理，就继续2
例：

a+b*(c-d)-e/f
abcd-*+ef/-

左优先原则：只要左边的运算符能先计算，就优先算左边的

中缀表达式转化为后缀表达式(机算)

规则

遇到操作数，直接加入后缀表达式
遇到界限符，遇到’(‘直接入栈，遇到’)’依次弹出栈内的运算符并加入后缀表达式，直到遇到’(‘为止。
注：**()不加入后缀表达式**
遇到运算符，，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并且加入后缀表达式，若碰到’)’或栈空则停止，再把当前运算符入栈。
处理完所有字符后，弹出所有运算符，并加入后缀表达式

代码

#define MAXSIZE 20
typedef struct{
    char data[MAXSIZE];
    int top;
}Stack;
void InitStack(Stack &S){
    S.top=-1;
}
bool Push(Stack &S,char x){
    if(S.top==MAXSIZE-1)return false;
    S.top++;
    S.data[S.top]=x;
    return true;
}
bool Pop(Stack &S,char &x){
    if(S.top==-1)return false;
    x=S.data[S.top];
    S.top--;
    return true;
}
bool StackEmpty(Stack S){
    if(S.top==-1)return true;
    else return false;
}
Stack Convert(char str[],int length){
    Stack S;
    char x;
    Stack s;
    InitStack(S);
    InitStack(s);
    for(int i=0;i<length;i++){
        if(str[i]>='0'&&str[i]<='9'){
            Push(s,str[i]);
        }
        if(str[i]=='('){
            Push(S,str[i]);
        }
        if(str[i]==')'){
            for(;S.data[S.top]!='(';){
                Pop(S,x);
                Push(s,x);
            }
            Pop(S,x);
        }
        if(str[i]=='+'||str[i]=='-'){
            for(;!StackEmpty(S)&&S.data[S.top]!='(';){
                Pop(S,x);
                Push(s,x);
            }
            Push(S,str[i]);
        }
        if(str[i]=='*'||str[i]=='/'){
            for(;!StackEmpty(S)&&(S.data[S.top]=='*'||S.data[S.top]=='/');){
                Pop(S,x);
                Push(s,x);
            }
            Push(S,str[i]);
        }
    }
    for(;!StackEmpty(S);){
      Pop(S,x);
      Push(s,x);
    }
    return s;
}

后缀表达式的计算(手算)

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数

后缀表达式的计算(机算)

规则

从左往右扫描下一个元素，直到处理完所有元素
若扫描到操作数则压入栈，并回到1，否则执行3
若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到1

代码

#define MAXSIZE 20
typedef struct{
    int data[MAXSIZE];
    int top;
}Stack;
void InitStack(Stack &S){
    S.top=-1;
}
bool Push(Stack &S,int x){
    if(S.top==MAXSIZE-1)return false;
    S.top++;
    S.data[S.top]=x;
    return true;
}
bool Pop(Stack &S,int &x){
    if(S.top==-1)return false;
    x=S.data[S.top];
    S.top--;
    return true;
}
int Calculate(char str[],int length){
    Stack S;
    InitStack(S);
    int a,b;
    for(int i=0;i<length;i++){
        if(str[i]>='0'&&str[i]<='9'){
            Push(S,str[i]-'0');
        }
        else {
            Pop(S,a);
            Pop(S,b);
            if(str[i]=='+'){
                Push(S,a+b);
            }
            if(str[i]=='-'){
                Push(S,b-a);
            }
            if(str[i]=='*'){
                Push(S,a*b);
            }
            if(str[i]=='/'){
                Push(S,b/a);
            }
        }
    }
    return S.data[S.top];
}

中缀表达式转化为前缀表达式(手算)

确定中缀表达式中各个运算符的运算顺序
选择下一运算符，按照[运算符左操作数右操作数]的方式组合成一个新的操作数
如果还有运算符没被处理，就继续2
右优先原则：只要右边的运算符能先计算，就先算右边的

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

规则

中缀转后缀+后缀表达式的计算 两种算法的结合
初始化两个栈，操作数栈和运算符栈
若扫描到操作数，压入操作数栈
若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

代码

int MidCalculate(char str[],int length){
    Stack S=Convert(str,length);
    char s[S.top+1];
    char x;
    length=S.top+1;
    for(int i=S.top;i>=0;i--){
        Pop(S,x);
        s[i]=x;
    }
    return Calculate(s,length);
}

递归

分析

特点：最后被调用的函数最先执行结束(LIFO)
函数调用时，需要用一个栈储存

调用返回地址
实参
局部变量

栈在递归中的应用

适合用递归算法解决：可以把原始问题转化为属性相同，但规模较小的问题

递归算法求阶乘
1
2
3
4
5
6
7
8
9
10
int factorial(int x){
if(x==1||x==0)
return 1;
else return x*factorial(x-1);
}
int main(){
//.....其他代码
int x=factorial(10);
return 0;
}
递归调用时，函数调用栈可称为递归工作栈
每进入一层递归，就将递归所需信息压入栈顶
每退出一层递归，就将栈顶信息弹出
缺点，太多层递归可能会造成栈溢出

递归算法求斐波那契数列

int Fib(int x){
    if(x==0)return 0;
    else if(x==1)return 1;
    else return Fib(x-1)+Fib(x-2);
}
int main(){
    //....其他代码
    int x=Fib(4);
    return 0;
}