栈的应用

括号匹配检验

 假如有字符串由"(){}[]"这几种括号组成，要你判断该字符串是否合法

步骤：

• 遇到左括号，入栈
• 遇到右括号，如果栈顶元素是右括号对应的左括号，出栈；否则，不合法，直接返回。

汉诺塔问题

直接上代码：

void move(char a, int b, char c){
    // 将编号为 b 的圆盘，从 a 移动到 c
}

// 将x上编号为 1~n 的圆盘移动到y， 借助z作为辅助塔
void hanoi(int n, char x, char y,char z){  
    if(n==1)
        move(x,1,z); 
    else{
        hanoi(n-1,x,z,y);
        move(x,n,z);
        hanoi(n-1,y,x,z);
    }
}

int main(){
    hanoi(n, x,y,z);
    return 0;
}

后缀表达式求值

 简单说明：栈只用来保存操作数

步骤：遇到

• 操作数：入栈
• 操作符c：出栈一个为b，再出栈一个为a，计算 a c b的结果，入栈
• 重复，最后结果为栈顶元素

C++代码：

int count(int a, char c, int b){
    switch(c){
        case '*': return a*b;
        case '/': return a/b;
        case '+': return a+b;
        case '-': return a-b;
    }
    return 0;
}
bool isOper(string &token){
	return token == "*" || token == "/" || token == "+" || token == "-";
}
int value(vector<string> tokens){
    stack<int> st;
    for(auto &token:tokens){
        if(isOper(token)){
            int num2 = st.top();st.pop();
            int num1 = st.top();st.pop();
            st.push(count(num1, token[0], num2));
        }else st.push(stoi(token));
    }
    return st.top();
}

中缀表达式转后缀表达式

讲解

 需要用到一个栈，用来存储操作符（括号算界限符，而非操作符）

步骤：

• 操作数：加入后缀表达式
• 界限符：‘(’ 直接入栈；‘)’ 依次弹出栈内运算符，直到 ‘(’，但是两种括号都直接丢弃，不需要加入后缀表达式中
• 运算符：依次弹出栈中高于或等于当前运算符优先级的所有运算符
• 重复，最后直到栈内所有运算符被弹出

代码

运算符优先级定量：

中缀表达式求值

 后缀表达式求值 + 中缀表达式转后缀表达式 = 中缀表达式求值

讲解

 需要两个栈，一个操作数栈，一个操作符栈（简称数栈和符栈）。

步骤：

• 操作数：入数栈
• 界限符：同中缀转后缀的步骤
• 操作符：同中缀转后缀的步骤
• 操作符出栈：运算数栈栈顶的两个操作数，并且结果入数栈
• 直到扫描完成以及符栈为空
• 结果为数栈顶部元素