数据结构重学日记（十四）栈的应用

括号匹配

假设有两种括号，一种圆的()，一种方的[]，嵌套顺序任意。

例如： ([]) ([][([])])

如果是左括号，则执行入栈操作，如果是右括号，出栈一个左括号判断是否与之匹配；直到最后全部匹配没有剩余则表示正确。

对之前栈的代码进行改造：

bool stack_check(SqStack *S, char *str) {
    int len = strlen(str);
    ElemType x;
    for (int i = 0; i < len; i++) {
        char a = str[i];
        switch (a) {
            case '(':
                push(S, a);
                break;
            case '[':
                push(S, a);
                break;
            case ')':
                pop(S, &x);
                if(x != '('){
                    printf("不匹配 \r\n");
                    return false;
                }
                break;
            case ']':
                pop(S, &x);
                if(x != '['){
                    printf("不匹配 \r\n");
                    return false;
                }
                break;

        }

    }
    if (stack_empty(S)){
        printf("空\r\n");
        return true;
    }else{
        return false;
    }
}

表达式求值

表达式

算数四则运算的规则：

• 先乘除后加减
• 从左到右
• 先括号内，再括号外

例如 ：
4 + 2 * 3 - 10 / 5 = 4 + 6 - 10 / 5 = 10 - 10 / 5 = 10 - 1 = 8

表达式包括前缀表达式、中缀表达式和后缀表达式，前缀表达式即运算符号在前数字在后，也称为波兰式，即 - * + 3 4 5 6。中缀表达式就是我们日常书写的形式，而后缀表达式则是数字在前符号在后，也称为逆波兰式。

在计算机中，前缀表达式和后缀表达式更容易处理和操作。

所以进行表达式求值，要先将中缀表达式转换成前缀或后缀表达式。当然也可以参考书上的算符优先级法，这个接下来再学习。

从左到右扫描表达式中的数字和符号，遇到数字就进栈，遇到符号则将栈顶元素出栈然后用这个符号进行运算，再将运算结果进栈，直到最后获得计算结果。

来个栗子，就算这个吧：(5 * 2 + 1 * 8) /2

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

待研究

手动转换：
((5 2)* (1 8)*) + 2 )/

int stack_eva(SqStack *S, char *str){
    int len = strlen(str);
    printf("len = %d\r\n",len);
    ElemType x,y;
    for (int i = 0; i < len; i++) {
        char a = str[i];
        switch (a) {
            case '+':
                pop(S, &x);
                pop(S, &y);
                push(S,x+y);
                printStack(S);
                break;
            case '-':
                pop(S, &x);
                pop(S, &y);
                push(S,x-y);
                printStack(S);
                break;
            case '*':
                pop(S, &x);
                pop(S, &y);
                push(S,x*y);
                printStack(S);
                break;
            case '/':
                pop(S, &x);
                pop(S, &y);
                push(S,y/x);
                printStack(S);
                break;
            default:
                push(S, a);
                printStack(S);
                break;

        }

    }

    return 0;
}

递归

如果在一个函数、过程或数据结构的定义中又应用了它自身，那么这个函数、过程或数据结构就称为递归定义的，简称递归。

int F(int n){
    if(n == 0) return 1;  // n == 0 f(0) ==1 递归边界
    else return n*F(n -1);  // 递归式 （F(n) = F(n -1) * n）
}

执行 F(3) = F(2) * 3 = F(1) * 2 * 3 = F(0) * 1 * 2 * 3 = 1 * 1 * 2 * 3 = 6

求斐波那契数列的第 n 项：

int fib(int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    else return fib(n - 1) + fib(n - 2);
}