Informatics Orsay all in one 1354: bracket matching test

【 Topic link 】

ybt 1354： Bracket match test

【 Topic test site 】

1. Stack

【 Their thinking 】

Traversal string , Left bracket in stack , When the right bracket is encountered , See if the top bracket and the right bracket can be paired . If both parentheses are parentheses or brackets , Then the two are paired , Left bracket out of stack . Otherwise, the brackets don't match .
If you traverse to the closing parenthesis , Stack empty found , Then there are closing parentheses that cannot be matched .
If at the end of the traversal , Stack is not empty. , Then there are left parentheses that cannot be matched .

【 Solution code 】

solution 1： Stack with array and expression

#include<bits/stdc++.h>
using namespace std;
int main()
{
    
	char s[260], stk[260];
	scanf("%s", s);
	int top = 0, len;
	len = strlen(s);
	for(int i = 0; i < len; ++i)
	{
    
		if(s[i] == '(' || s[i] == '[')// Left bracket in stack  
			stk[++top] = s[i];
		else if(s[i] == ')' || s[i] == ']')
		{
    
			if(top == 0 || 
                s[i] == ')' && stk[top] != '(' ||
                s[i] == ']' && stk[top] != '[')// Empty stack or unmatched parentheses  
			{
    
				printf("Wrong");// Unable to pair  
				return 0;
			}
			else
				top--;
		}
	}
	if(top == 0)// If the stack is not empty , Cannot pair  
		printf("OK");
	else
		printf("Wrong");
	return 0;
}

solution 2： Use C++ STL

#include<bits/stdc++.h>
using namespace std;
int main()
{
    
	string s;
	cin >> s;
	stack<char> stk;
	for(int i = 0; i < s.length(); ++i)
	{
    
		if(s[i] == '(' || s[i] == '[')// Left bracket in stack  
			stk.push(s[i]);
		else if(s[i] == ')' || s[i] == ']')
		{
    
			if(stk.empty() || 
                s[i] == ')' && stk.top() != '(' ||
                s[i] == ']' && stk.top() != '[')// Empty stack or unmatched parentheses  
			{
    
				cout << "Wrong";// Unable to pair  
				return 0;
			}
			else
				stk.pop();
		}
	}
	if(stk.empty())// If the stack is not empty , Cannot pair  
		cout << "OK";
	else
		cout << "Wrong";
	return 0;
}