数据结构与算法之-----栈的应用（二）

前言

写在前面的话：数据结构与算法。

1. 对于初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到同tag前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们按顺序进行学习；

2. 对于想查询有关资料的小伙伴们，可以选择性地浏览。希望大家都能有所收获～

栈的应用（二）

本章我们来看看栈的第二个应用：

问提描述：如何判断一个表达式中的 (), [], {} 是否匹配？

比如，表达式“ 3*(8+3*2) ”是匹配的，表达式“ (3*4+33 ”是不匹配的。

问题解决（ParenMatch.h）：

/*
 * 作者：易果啥笔
 * 时间：2021.8.20
 * 内容：栈的典型应用二：判断括号(),[],{}是否匹配
 *
 */

#ifndef STACK_PARENMATCH_H
#define STACK_PARENMATCH_H
#include "Stack.h"

//length()函数用于求数组中表达式的字符数
int length(const char exp[]){
    static int count = 0;
    for(int i = 0 ; exp[i]!='\0'; i++){
        count++;
    }
    return count;
}


//trans()函数将bool值转换为人性化语言
void trans(bool _bool) {
    if(_bool)cout<<"匹配"<<endl;
    else cout<<"不匹配"<<endl;
}


//paren()函数用于判断表达式中括号是否匹配
bool paren(const char exp[],int lo,int hi) {
    Stack<char> S;
    for(int i = lo ; i < hi ; i++){
        switch (exp[i]) {
            case '(' :
            case '[' :
            case '{' : S.push(exp[i]); break;
            case ')' :if( ( S.Empty() ) || ( '(' != S.pop() )) return false; break;
            case ']' :if( ( S.Empty() ) || ( '[' != S.pop() )) return false; break;
            case '}' :if( ( S.Empty() ) || ( '{' != S.pop() )) return false; break;
            default: break;
        }
    }

    return S.Empty();
}

#endif //STACK_PARENMATCH_H

匹配算法的核心思想是，一旦遇到左括号(, [, {,便将其压入栈中；如果遇到右括号), ], },便验证此时它前面的括号（也就是栈顶元素）是否与之匹配，如果不匹配，直接返回false；如果匹配，继续往下扫描，直至栈为空。

我们来验证此算法的正确性：

/*
 * 作者：易果啥笔
 * 时间：2021.8.20
 * 内容：栈的应用
 *
 */

#include <iostream>
#include "Stack.h"
#include "ParenMatch.h"
using namespace std;

//遍历函数print
template <typename T> void print(T& e){ cout<<e; };

int main() {
    

    //应用二：判断一个表达式中括号(),[],{}是否匹配
    char expression1[40] = "(1+23*4-56*7))";
    cout<<"'(1+23*4-56*7))'中的括号是否匹配？：";trans(paren(expression1,0,length(expression1)));

    return 0;
}