SPOJ Solution-Brackets-Solution in C, C++, Java, Python

Algorithm

Problem link- https://www.spoj.com/problems/BRCKTS/

BRCKTS - Brackets

We will call a bracket word any word constructed out of two sorts of characters: the opening bracket "(" and the closing bracket ")". Among these words we will distinguish correct bracket expressions. These are such bracket words in which the brackets can be matched into pairs such that

every pair consists of an opening bracket and a closing bracket appearing further in the bracket word
for every pair the part of the word between the brackets of this pair has equal number of opening and closing brackets

On a bracket word one can do the following operations:

replacement -- changes the i-th bracket into the opposite one
check -- if the word is a correct bracket expression

Task

Write a program which

reads (from standard input) the bracket word and the sequence of operations performed,
for every check operation determines if the current bracket word is a correct bracket expression,
writes out the outcome (to standard output).

Input

Ten test cases (given one under another, you have to process all!). Each of the test cases is a series of lines. The first line of a test consists of a single number n (1<=n<=30000) denoting the length of the bracket word. The second line consists of n brackets, not separated by any spaces. The third line consists of a single number m -- the number of operations. Each of the following m lines carries a number k denoting the operation performed. k=0 denotes the check operation, k>0 denotes replacement of k-th bracket by the opposite.

Output

For every test case your program should print a line:
Test i:
where i is replaced by the number of the test and in the following lines, for every check operation in the i-th test your program should print a line with the word YES, if the current bracket word is a correct bracket expression, and a line with a word NO otherwise. (There should be as many lines as check operations in the test.)

Example

Input:
4
()((
4
4
0
2
0
[and 9 test cases more]
Output:
Test 1:
YES
NO
[and 9 test cases more]

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 3e4+5;
struct Tree{int uOB, uCB;};
Tree T[4*MAXN];
char s[MAXN];
int n;

void build(int node, int start, int end){
	if(start > end)
		return;
	if(start == end){
		if(s[start] == '('){
			T[node].uOB = 1;
			T[node].uCB = 0;
		}else{
			T[node].uCB = 1;
			T[node].uOB = 0;
		}
		return;
	}
	int mid = (start + end) >> 1;
	int left = node << 1, right = left + 1;
	build(left, start, mid);
	build(right, mid + 1, end);
	int matches = min(T[left].uOB, T[right].uCB);
	T[node].uOB = T[right].uOB + (T[left].uOB - matches);
	T[node].uCB = T[left].uCB + (T[right].uCB - matches);
}

void update(int node, int start, int end, int idx){
	if(start > end)
		return;
	if(start == end){
		if(s[start] == '('){
			s[start] = ')';
			T[node].uCB = 1;
			T[node].uOB = 0;
		}else{
			s[start] = '(';
			T[node].uOB = 1;
			T[node].uCB = 0;
		}
		return;
	}
	int mid = (start + end) >> 1;
	int left = node << 1, right = left + 1;
	if(idx <= mid)
		update(left, start, mid, idx);
	else
		update(right, mid + 1, end, idx);
	int matches = min(T[left].uOB, T[right].uCB);
	T[node].uOB = T[right].uOB + (T[left].uOB - matches);
	T[node].uCB = T[left].uCB + (T[right].uCB - matches);
}

int main(){
	// io;
	for(int i = 1;i <= 10; i++){
		for(int j = 1;j < 4*MAXN; j++){
			T[j].uOB = T[j].uCB = 0;
		}
		printf("Test %d:\n", i);
		scanf("%d ", &n);
		scanf("%s", s);
		build(1, 0, n-1);
		int q;
		scanf("%d", &q);
		while(q--){
			int x;
			scanf("%d", &x);
			if(x > 0){
				x--;
				update(1, 0, n-1, x);
			}else{
				if(T[1].uOB == 0 && T[1].uCB == 0)
					printf("YES\n");
				else
					printf("NO\n");
			}
		}
	}
	return 0;
}

Copy The Code & Try With Live Editor

Input

–

cmd

4
()((
4
4
0
2
0
[and 9 test cases more]

Output

–

cmd

Test 1:
YES
NO
[and 9 test cases more]

#2 Code Example with Java Programming

Code - Java Programming

package com.segment;

import java.io.PrintWriter;

import com.io.FasterScanner;

/**
 * http://www.spoj.com/problems/BRCKTS/
 * 
 * AC :)
 * 
 * @author doom
 * 
 */

public class Brackets {

	public FasterScanner mFScanner;
	public PrintWriter mOut;
	public int N;
	public int M;
	public int MAXN;
	public Node mTree[];
	public int A[];

	public Brackets() {
		mFScanner = new FasterScanner();
		mOut = new PrintWriter(System.out);
	}

	public void initSegmentTree() {
		MAXN = N;
		MAXN = MAXN | (MAXN >> 1);
		MAXN = MAXN | (MAXN >> 2);
		MAXN = MAXN | (MAXN >> 4);
		MAXN = MAXN | (MAXN >> 8);
		MAXN = MAXN | (MAXN >> 16);
		MAXN = (MAXN + 1) << 1;
		mTree = new Node[MAXN];
	}

	public void buildSegmentTree(int node, int begin, int end) {
		int mid;

		if (begin == end) {
			int open, close;
			open = close = 0;
			if (A[begin] == -1)
				open = 1;
			else
				close = 1;
			mTree[node] = new Node(open, close);
			return;
		}

		mid = begin + ((end - begin) >> 1);

		buildSegmentTree(2 * node, begin, mid);
		buildSegmentTree(2 * node + 1, mid + 1, end);

		mTree[node] = new Node();
		mTree[node].merge(mTree[2 * node], mTree[2 * node + 1]);

	}

	public Node query(int node, int begin, int end, int qBegin, int qEnd) {
		int mid;
		Node left, right, n;

		if (qEnd < begin || qBegin > end)
			return null;

		if (qBegin <= begin && qEnd >= end)
			return mTree[node];

		mid = begin + ((end - begin) >> 1);

		left = right = null;

		left = query(2 * node, begin, mid, qBegin, qEnd);
		right = query(2 * node + 1, mid + 1, end, qBegin, qEnd);

		if (left == null)
			return right;

		if (right == null)
			return left;

		n = new Node();

		n.merge(left, right);

		return n;
	}

	public void updateValue(int node, int begin, int end, int index) {
		int mid;

		if (begin == end) {
			mTree[node].reverse();
			return;
		}

		mid = begin + ((end - begin) >> 1);

		if (index >= begin && index <= mid)
			updateValue(2 * node, begin, mid, index);
		if (index > mid && index <= end)
			updateValue(2 * node + 1, mid + 1, end, index);

		mTree[node].merge(mTree[2 * node], mTree[2 * node + 1]);
	}

	public String check(Node node) {

		// mOut.println(node.open + " " + node.close);
		if (node.open == node.close && node.open == 0 && node.close == 0)
			return "YES";

		return "NO";
	}

	public void solve() {
		int i;
		int input;
		int index;
		int test;
		Node node;
		String str;
		StringBuilder strB;

		for (test = 1; test <= 10; test++) {

			N = mFScanner.nextInt();
			A = new int[N];
			initSegmentTree();

			str = mFScanner.nextLine();

			for (i = 0; i < N; i++) {
				if (str.charAt(i) == '(')
					A[i] = -1;
				else
					A[i] = 1;
			}

			buildSegmentTree(1, 0, N - 1);

			M = mFScanner.nextInt();
			strB = new StringBuilder(M);

			for (i = 0; i < M; i++) {
				input = mFScanner.nextInt();

				if (input == 0) {
					node = query(1, 0, N - 1, 0, N - 1);
					strB.append(check(node));
					strB.append("\n");
				} else {
					index = input - 1;
					updateValue(1, 0, N - 1, index);
				}
			}
			mOut.println("Test " + test + ":");
			mOut.print(strB);
			mOut.flush();
		}

		close();

	}

	public void close() {
		mOut.flush();
		mOut.close();
	}

	class Node {
		int open;
		int close;

		public Node() {
			open = close = 0;
		}

		public Node(int open, int close) {
			this.open = open;
			this.close = close;
		}

		public void reverse() {
			open = 1 - open;
			close = 1 - close;
		}

		public void merge(Node left, Node right) {
			int min;
			min = Math.min(left.open, right.close);
			this.open = left.open + right.open - min;
			this.close = left.close + right.close - min;
		}
	}

	public static void main(String[] args) {
		Brackets mSol = new Brackets();
		mSol.solve();
	}
}

Copy The Code & Try With Live Editor

Input

–

cmd

4
()((
4
4
0
2
0
[and 9 test cases more]

Output

–

cmd

Test 1:
YES
NO
[and 9 test cases more]

Demonstration

SPOJ Solution-Brackets-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python

Try With Live Editor

Category - Sphere Online Judge Maniruzzaman Akash 1 year ago 337 0