(데이터 구조 정리) NJUPT 1054

이 블 로 그 는 OJ 의 제목 을 매개체 로 데이터 구 조 를 정리 했다.계속 업데이트 되 는데...
    데이터 구조의 유연 한 응용 이 때때로 문제 의 해답 을 간소화 할 수 있다 는 것 을 우 리 는 모두 알 고 있다.
 
    창고
     1. NJUPT OJ 1054 (회 문 꼬치 의 판단)
     리 턴 문자열 의 판단: 한 문자열 의 절반 을 하나의 스 택 에 저장 한 다음 스 택 꼭대기 에서 이 문자열 이 리 턴 문자열 인지 아 닌 지 를 판단 합 니 다.
     

/*
 * NJUPTOJ_1054.cpp
 *
 *  Created on: 2014 5 22 
 *      Author: pc
 */

#include <iostream>
#include <cstdio>

using namespace std;


const int maxn = 300;

void toLower(char arr[],int len){
	int i;
	for(i = 0 ; i < len ; ++i){
		if(!islower(arr[i])){
			arr[i] += 32;
		}
	}
}


int main(){
	char a[maxn];
	char s[maxn];

	while(gets(a)!=NULL){


		int len = strlen(a);
		toLower(a,len);

		int mid = len/2 - 1;

		int top = 0;
		int i;
		for(i = 0 ; i <= mid ; ++i){
			s[++top] = a[i];
		}


		int next;
		if(len%2 == 0){
			next = mid+1;
		}else{
			next = mid+2;
		}

		for(i = next ; i <= len-1 ; ++i){
			if(s[top] != a[i]){
				break;
			}

			--top;
		}

		if(top != 0){
			printf("Not Palindrome.
");
		}else{
			printf("Bingle! Palindrome.
");
		}
	}

	return 0;

}

다음은 이 문 제 를 다시 풀 때의 코드 입 니 다.

/*
 * njupt_1054_1.cpp
 *
 *  Created on: 2014 9 6 
 *      Author: pc
 */


#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 300;


/**
 *            
 */
void toLower(char a[]){
	int len = strlen(a);
	int i;
	for(i = 0 ; i < len ; ++i){
		if(islower(a[i]) == false){
			a[i] += 32;
		}
	}
}


void work(char a[]){

	int len = strlen(a);
	int s[len];

	/**
	 *  mid next   :
	 *mid:                  
	 *next:                             
	 */
	int mid = len/2 - 1;
	int next;
	if(len%2 == 0){
		next = mid+1;
	}else{
		next = mid+2;
	}

	int top = 0;
	int i;
	for(i = 0 ; i <= mid ; ++i){
		s[++top] = a[i];
	}

	for(i = next ; i <= len-1 ; ++i){
		if(s[top] != a[i]){
			break;
		}

		--top;
	}


	if(top == 0){
		printf("Bingle! Palindrome.
");
	}else{
		printf("Not Palindrome.
");
	}

}

int main(){

	char s[maxn];

	/**
	 *               ...
	 */
	while(gets(s) != NULL){
		toLower(s);
		work(s);
	}

	return 0;

}

2, NEFU OJ 194 답장 문자열
산법 사상 은 위의 것 과 같다.

/*
 * NEFU_194.cpp
 *
 *  Created on: 2014 5 23 
 *      Author: pc
 */

#include <iostream>
#include <cstdio>

using namespace std;

string a;
string s;

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {

		cin >> a;
		int len = a.length();


		int mid = len / 2 - 1;

		int top = 0;
		int i;


		for (i = 0; i <= mid; ++i) {
			top += 1;
			s[top] = a[i];
		}


		int next;
		if (len % 2 == 0) {
			next = mid + 1;
		} else {
			next = mid + 2;
		}


		for (i = next; i <= len - 1; ++i) {
			if (s[top] != a[i]) {
				break;
			}

			--top;
		}

		if (top != 0) {
			printf("NO
");
		} else {
			printf("YES
");
		}
	}

	return 0;
}

3. NYOJ 1002 괄호 의 일치
사상: 만약 에 입력 한 기호 가 (, [바로 스 택 에 들 어 갑 니 다. 만약 에] 라면 이 일의 마지막 이 [, 만약 에 [스 택 에서 나 갑 니 다. 그렇지 않 으 면] 스 택 에 들 어 갑 니 다.

/*
 * NY_2_1.cpp
 *
 *  Created on: 2014 5 25 
 *      Author: pc
 */


#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;


int main(){

	string a;
	int t;
	scanf("%d",&t);
	while(t--){
		stack<char> s;

		cin >> a;
		int len = a.length();
		int i;
		for(i = 0 ; i < len ; ++i){
			if(a[i] == '(' || a[i] == '['){
				s.push(a[i]);
			}else if(a[i] == ')'){
				if(!s.empty() && s.top() == '('){
					s.pop();
				}else{
					s.push(a[i]);
				}
			}else if(a[i] == ']'){
				if(!s.empty() && s.top() == '['){
					s.pop();
				}else{
					s.push(a[i]);
				}
			}
		}

		if(s.empty()){
			printf("Yes
");
		}else{
			printf("No
");
		}
	}

	return 0;
}