FB - Xử lí ngoặc

18/05/2023

Link facebook

Thuật

gọi mảng st để lưu các ngoặc (, {, [, và n số lượng phần tử mà mảng đang lưu trữ (ban đầu n = 0)

gán ok= "true"

ta sẽ duyệt từ 1 -> length(s):

  • Nếu như s[i] in [{, [, (] thì ta tiến hành st[n] = s[i], inc(n);

  • Ngược lại ta tiến hành kiểm tra

    • nếu như n = 0 (trường hợp trong mảng chưa lưu ngoặc nào) thì ta dừng lặp và in ra ok = "false"
    • ngược lại ta duyệt từ 0 -> n-1 trong mảng st và nếu như có ngoặc thỏa mãn với ngoặc đóng s[i] thì ta dừng lặp và bỏ phần tử đó ra ngoài. Ngược lại (nếu ko có ngoặc mở trong mảng st nào thỏa mãn với s[i]) thì dừng lặp và in ra ok = "false"

khi duyệt xong ta in ra ok tương ứng với kết quả

Code
#include <bits/stdc++.h>
#define hieuhfgr ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define gcd __gcd
#define pb push_back
#define fi first
#define se second
#define oo 1e9;
#define endl "\n"
#define inputfile "BAI1.INP"
#define outputfile "BAI1.OUT"
#define file freopen(inputfile, "r", stdin);freopen(outputfile, "w", stdout)
using namespace std;

int main()
{
	hieuhfgr;
	file;
	string s;
	cin >> s;
	string res = "true";
	vector<char> st;
	for (int i=0 ; i < s.length();i++) {
		if (s[i] == '{' || s[i] == '(' || s[i] == '[') st.pb(s[i]);
		else {
			if(st.empty()) {
				res = "false";
				break;
			} else{
				int pos=-1;
				for (int j = 0; j < st.size(); j++) {
					string tmp = "";
					tmp += st[j];
					tmp += " ";
					tmp += s[i];
					if (tmp == "{ }" || tmp == "( )" || tmp == "[ ]") {
						pos = j;
						break;
					}
				}
				if (pos == -1) {
					res="false";
					break;
				} else {
					st[pos] = 'x';
				}
			}
		}
	}
	cout << res;
	return 0;
}