表达式括号匹配

链接

这题会输入一段表达式,要求我们判断括号能不能匹配

比如2+(23-1*7))

这个肯定是不匹配的,我们所需要做的就是判断这些括号能不能对应上

因此,我们不必在意其他无关变量

我们可以设置一个计数器,当我们遇到左括号时,计数器加一,遇到右括号但计数器为0时,说明

此刻的右括号多了(可能整体相等但此时多了,就像")("这样)

那直接就返回NO了

如果最后计数器不等于0,说明左右括号数量不相等,那也是NO

#include<bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    int m=str.size();
    int ok=0;
    for(int i=0;i<m;i++){
        if(str[i]=='('){
            ok++;
        }
        else if(str[i]==')'&&ok!=0){
          ok--;
        }
        else if(str[i]==')'&&ok==0){
            ok=1000;
            break;
        }
    }
    if(ok==0){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

时间复杂度:O(n)

空间复杂度:O(n)