G17|表达式括号匹配2题解

G17|表达式括号匹配2题解

较详细题解(具体讲解在代码里)

使用基础STL栈

·st.push(x)//入栈
·st.empty()//判断栈是否为空?
·st.pop()//删除最顶值

综上，写出代码：

#include<iostream>
#include<stack>
using namespace std;

//初始化定义
stack<char> st;
string s;

int main(){
    //输入
    cin>>s;

    //遍历判断
    for(int i = 0;i < s.size();i++){
        if(s[i] == '(')
            st.push(s[i]);//统计"("的数量
        if(s[i] == ')'){
            if(!st.empty())//有没有"("抵消?
                st.pop();//有,抵消
            else{
                cout<<"NO";//必须要有一个"("在")"前面,否则判否结束
                return 0;
            }
        }
    }
    if(st.empty())//判断是否抵消完?
        cout<<"YES";
    else
        cout<<"NO";
    return 0;
}

时间复杂度是

O(n)