考研算法辅导课笔记（四）

2.2栈和队列的应用

2.2.1栈的应用

表达式求值（中缀表达式转后缀表达式、括号匹配）、DFS。

DFS也就是递归，有一类特殊的递归：尾递归。

尾递归：

若函数在尾位置调用自身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归。尾递归也是递归的一种特殊情形。

考点：尾递归可以等价于迭代写法，不需要用栈来实现。

#include <iostream>
using namespace std;

void f(int n){

    if (n <= 0) return ;
    printf("%d\n",n);

    f(n-1); // 尾递归，在尾部递归调用
}

int main(){

    f(7);

    cout << "-----------\n";
    // 等价于迭代写法，不需要用栈来实现
    // 当递归需要回溯去执行剩下的操作时，需要用栈来存储信息
    for (int i = 7; i; -- i) cout << i << '\n';
    return 0;
}

出栈顺序：

参考文章1： https://oi-wiki.org/math/combinatorics/catalan/。

参考文章2： https://zhuanlan.zhihu.com/p/391237550。

一个栈（无穷大）的进栈序列为1,2,3,…,n，有多少个不同的出栈序列？

这是一个Catalan 数列问题，卡特兰数。

答案是： $\frac {\binom{2n}{n}} {n+1}$.

表达式求值：

3302. 表达式求值

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：
数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中，均不超过 2^31−1。
题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。
C++和Java中的整除默认是向零取整；Python中的整除"//"默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式
共一行，为给定表达式。

输出格式
共一行，为表达式的结果。

数据范围
表达式的长度不超过 10^5。

输入样例：
(2+2)*(1+1)
输出样例：
8

题解详见算法基础课笔记（十四）。

考研中代码不一定要完全会写（推荐最好熟练掌握），但是表达式求值的流程一定要牢牢掌握。

使用两个栈来求表达式的值，一个操作数栈，一个操作符栈。

先背上面思路，再背下面代码。

#include <iostream>
#include <stack>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

stack<int> num;
stack<char> op;

void eval(){
    auto b = num.top();num.pop();
    auto a = num.top();num.pop();
    auto c = op.top();op.pop();
    
    int x;
    if (c == '+') x = a + b;
    if (c == '-') x = a - b;
    if (c == '*') x = a * b;
    if (c == '/') x = a / b;
    num.push(x);
}    

int main(){
    
    unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};
    
    string str;
    cin >> str;
    
    for (int i = 0;i < str.size();i ++){
        char c = str[i];
        if (isdigit(c)){
            int x = 0,j = i;
            while (j < str.size() && isdigit(str[j])) x = x*10 + str[j++] - '0';
            i = j-1;
            num.push(x);
        }
        
        else if (c == '(') op.push(c);
        else if (c == ')'){
            while (op.top() != '(') eval();
            op.pop();
        }
        else{
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    
    while (op.size()) eval();
    
    cout << num.top() << '\n';
    return 0;
}

中缀表达式转后缀表达式：

只需要将上面的程序修改一下就行了。

不需要数栈，遇到数直接输出就行，进行运算时直接输出运算符。

#include <iostream>
#include <stack>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

stack<char> op;

void eval(){
    auto c = op.top();op.pop();
    cout << c << ' ';
}    

int main(){
    
    unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};
    
    string str;
    cin >> str;
    
    for (int i = 0;i < str.size();i ++){
        char c = str[i];
        if (isdigit(c)){
            int x = 0,j = i;
            while (j < str.size() && isdigit(str[j])) x = x*10 + str[j++] - '0';
            i = j-1;
            cout << x << ' ';
        }
        
        else if (c == '(') op.push(c);
        else if (c == ')'){
            while (op.top() != '(') eval();
            op.pop();
        }
        else{
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    
    while (op.size()) eval();
    // input:  (2+2)*(1+1)
	// output:  2 2 + 1 1 + * 
    return 0;
}