Informatics Orsay all in one 1353: expression bracket matching | Luogu p1739 expression bracket matching

【 Topic link 】

ybt 1353： Expression brackets match (stack)
Luogu P1739 Expression brackets match

【 Topic test site 】

1. Stack

【 Their thinking 】

Traversing the entire string , When an open bracket is encountered, it is pushed to the stack , When the right bracket is encountered , A left parenthesis should appear on the stack . If the stack is empty when the closing bracket is encountered , Description there are closing parentheses that cannot be paired .
At the end of the traversal , If the stack is not empty , Description there are left parentheses that cannot be paired .

You can use arrays and expressions to implement stack functions , You can use functions to implement stack functions , You can write your own stack class , You can also use STL Medium is stack.

【 Solution code 】

solution 1： Stack with array and expression

#include<bits/stdc++.h>
using namespace std;
int main()
{
    
    char s[260];
    char stk[260];
    int top = 0;
    scanf("%s", s);
    bool isMatch = true;
    for(int i = 0; s[i] != '@'; ++i)
    {
    
        if(s[i] == '(')
            stk[++top] = s[i];// Push  
        else if(s[i] == ')')
        {
    
            if(top == 0)// Judge whether the stack is empty . Empty stack encountered with closing parenthesis  
            {
    
                isMatch = false;
                break;
            }
            else
                --top;// Out of the stack  
        }
    }
    if(top != 0)// If the last stack is not empty  
        isMatch = false;
    if(isMatch)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

solution 2： Function to realize stack function

#include<bits/stdc++.h>
using namespace std;
char stk[260];
int top = 0;
void push(char c)
{
    
    stk[++top] = c;
}
bool empty()
{
    
    return top == 0; 
}
void pop()
{
    
    top--;
}
int main()
{
    
    char s[260];
    scanf("%s", s);
    bool isMatch = true;
    for(int i = 0; s[i] != '@'; ++i)
    {
    
        if(s[i] == '(')
            push(s[i]);// Push  
        else if(s[i] == ')')
        {
    
            if(empty())// Judge whether the stack is empty . Empty stack encountered with closing parenthesis  
            {
    
                isMatch = false;
                break;
            }
            else
                pop();// Out of the stack  
        }
    }
    if(empty() == false)// If the last stack is not empty  
        isMatch = false;
    if(isMatch)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

solution 3：C++STL Realize stack function

#include<bits/stdc++.h>
using namespace std;
int main()
{
    
    char s[260];
    scanf("%s", s);
    stack<char> stk;
    bool isMatch = true;
    for(int i = 0; s[i] != '@'; ++i)
    {
    
        if(s[i] == '(')
            stk.push(s[i]);// Push  
        else if(s[i] == ')')
        {
    
            if(stk.empty())// Judge whether the stack is empty . Empty stack encountered with closing parenthesis  
            {
    
                isMatch = false;
                break;
            }
            else
                stk.pop();// Out of the stack  
        }
    }
    if(stk.empty() == false)// If the last stack is not empty  
        isMatch = false;
    if(isMatch)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}