문제 소개
사용자로부터 식을 입력 받아 유효하게 입력되었는지 검사하는 프로그램이다.
여기서의 유효한 식이란 아래의 조건을 만족하는 것을 의미한다.
① 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 일치한다.
② 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
③ 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호는 서로를 교차하지 않는다.
왜 스택인가
스택을 사용하면 주어진 식에서 왼쪽 괄호가 등장했을 때는 스택에 저장한다. 반면 오른쪽 괄호가 등장했을 때에는 스택에서 데이터를 꺼내 등장한 괄호와 짝이 맞는지 검사한다.
스택을 사용하는 이유는 가장 최근에 등장한 괄호의 짝이 새로 등장한 괄호와 일치해야 하기 때문이다. 즉, 나중에 저장된 데이터를 먼저 꺼내서 확인해야 하기 때문에 스택을 유용하게 사용할 수 있다.
구현하기
스택을 용도에 맞게 수정하기
스택을 구현하는 과정은 이전 게시물에서 소개했기 때문에 따로 언급하지 않을 것이다. 해당 내용은 아래의 링크에서 확인할 수 있다.
[Data Structure] 스택(Stack) 구현하기 (새 창)
지난 번에 구현한 스택을 이번 문제 상황에 맞게 수정할 것이다.
DataType.h
DataType.h는 스택에 저장할 구조체인 Element를 정의하는 헤더 파일이다.
기존에는 Element가 문자열(name)과 정수(age)로 구성했으나, 문제 상황에서는 괄호를 저장해야 하므로 아래와 같이 수정하였다.
#pragma once
#define TRUE 1
#define FALSE 0
typedef char Element; // 배열 요소의 자료형 정의DynamicArray의 배열 수정
기존에는 DynamicArray를 포인터들의 배열 즉, 이중 포인터로 정의하였으나, 위처럼 요소 Element가 char로 바뀌면서 구조체를 사용할 필요가 없어졌고 따라서 동적 배열을 포인터들의 배열이 아닌 Element형 배열(=char형 배열)로 수정해주었다.
이에 따라 대부분의 함수가 포인터를 사용하지 않게 되면서 전체적인 수정이 있었으나 여기에 모두 언급하진 않겠다.
Stack.c
Element에 대한 정의가 바뀌었기 때문에 Stack.c 파일의 일부를 수정해야 한다.
Stack.c 파일에는 스택의 데이터를 출력하는 StkPrint() 함수가 존재한다. 기존에는 Element의 name과 age를 출력하는 함수였으나 아래와 같이 수정하였다.
void StkPrint(const Stack* stack)
{
if (stack != NULL) {
for (int i = stack->top; i >= 0; i--) {
Element tmp = DAGet(stack->darr, i);
printf("%c\n", tmp);
}
}
}DynamicArray.c
바로 위에서 출력 함수를 수정해준 것처럼 DynamicArray.c에도 출력 함수 DAPrint()가 존재하기 때문에 이를 수정해주었다.
void DAPrint(const DynamicArray* darr)
{
for (int i = 0; i <= darr->index; i++)
printf("%c\n", darr->arr[i]);
}main.c
이번엔 main 함수를 수정해야 한다. 기존의 main 함수는 스택이 정상적으로 작동하는지 테스트하기 위한 목적의 함수였으나 이번엔 문자열을 입력 받아 유효성을 검사하는 함수를 호출하는 방식으로 수정하였다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include "Stack.h"
#include "vld.h"
#define MAX_LEN 100
int isValidExp(char str[]); // 유효한 식인지 검사하는 함수
int main(void)
{
char userExp[MAX_LEN];
while (TRUE) {
printf("문자열을 입력하세요(/q: 종료): ");
scanf("%[^\n]s", userExp);
if (!strncmp(userExp, "/q", 2))
break;
printf("입력한 문자열: %s\n", userExp);
//if (isValidExp(userExp) == TRUE)
// printf("유효한 식입니다.\n");
//else printf("유효하지 않은 식입니다.\n");
while(getchar()!='\n'); // 입력 버퍼를 비운다.
}
}사용자가 검사하고자 하는 식을 계속해서 입력할 수 있도록 무한 루프를 돌렸다.
만약 식을 입력하지 않고 "/q"라고 입력한다면 무한 루프에서 빠져나와 프로그램이 종료된다.
isValidExp() 함수는 매개 변수로 전달 받은 문자열이 유효한 식인지 검사한다. 반환형은 int로 두어 유효하면 1(TRUE), 유효하지 않다면 0(FALSE)를 반환하도록 하였다. 이 함수는 아래의 '문제 해결하기'에서 소개한다.
C6054 경고 발생
입력 가능한 식의 최대 길이는 MAX_LEN 즉, 100자리이다. 널문자를 포함하면 99자까지 입력해야 오류를 일으키지 않는다. 사용자가 이것을 지킬 것이란 보장이 없기 때문에 strncmp() 함수에 아래와 같은 경고가 나타난다.
C6054: 'userExp' 문자열이 0으로 종료되지 않을 수 있습니다.경고를 없애려 했으나 생각보다 시간이 지체되었고 이 경고에 대해 잘 이해하고 있기 때문에 일단 무시하기로 했다.
실행 화면
isValidExp() 함수를 정의하기 전이기 때문에 main 함수에서 이 부분만 주석처리하고 테스트를 진행했다.
Visual Leak Detector read settings from: C:\Program Files (x86)\Visual Leak Detector\vld.ini
Visual Leak Detector Version 2.5.1 installed.
문자열을 입력하세요(/q: 종료): Testing
입력한 문자열: Testing
문자열을 입력하세요(/q: 종료): black sheep wall
입력한 문자열: black sheep wall
문자열을 입력하세요(/q: 종료): testing main function
입력한 문자열: testing main function
문자열을 입력하세요(/q: 종료): /q
No memory leaks detected.
Visual Leak Detector is now exiting.
C:\Users\Hotaek\Desktop\2학년 여름\DS_Review\Stack\ParenthesesChecker\Debug\ParenthesesChecker.exe(프로세스 20108개)이( 가) 종료되었습니다(코드: 0개).
이 창을 닫으려면 아무 키나 누르세요...
띄어쓰기가 포함된 문자열도 정상적으로 입력된다.
/q 역시 잘 작동한다.
문제 해결하기
int isValidExp() 함수 전체 코드
int isValidExp(char str[]) // 유효한 식인지 검사하는 함수
{
Stack* stack = StkCreate();
// 메모리가 부족하여 할당받지 못한 경우 유효한 식인지 알 수 없었으므로 -1을 반환한다.
if (stack == NULL) return -1;
for (int i = 0; str[i] != '\0'; i++) { // 문자열의 한 글자씩 불러온다.
char ch = str[i];
if (ch == '(' || ch == '{' || ch == '[') {
StkStore(stack, ch);
}
else if (ch == ')' || ch == '}' || ch == ']') {
Element tmp = StkPop(stack);
if (tmp == 0) { // 조건 2 위배
StkDestroy(stack);
return FALSE;
}
switch (ch) { // 조건 3을 만족하는지 검사
case ')': if (tmp == '(') break;
case '}': if (tmp == '{') break;
case ']': if (tmp == '[') break;
default:
StkDestroy(stack);
return FALSE;
}
}
else continue; // 괄호가 아닌 문자는 고려하지 않는다.
}
if (StkIsEmpty(stack)) {
StkDestroy(stack);
return TRUE;
}
else {
StkDestroy(stack);
return FALSE;
}
}실행 결과
Visual Leak Detector read settings from: C:\Program Files (x86)\Visual Leak Detector\vld.ini
Visual Leak Detector Version 2.5.1 installed.
문자열을 입력하세요(/q: 종료): ()
유효한 식입니다.
문자열을 입력하세요(/q: 종료): )
유효하지 않은 식입니다.
문자열을 입력하세요(/q: 종료): (())(
유효하지 않은 식입니다.
문자열을 입력하세요(/q: 종료): {}{()(){}}
유효한 식입니다.
문자열을 입력하세요(/q: 종료): [{}][()(){}]
유효한 식입니다.
문자열을 입력하세요(/q: 종료): {36/(28/7)+10}*4
유효한 식입니다.
문자열을 입력하세요(/q: 종료): [{71-5*(32-25)}/9+3]-[3*{(31-3)/2-5}]
유효한 식입니다.
문자열을 입력하세요(/q: 종료): [{71-5*(32-25)}/9+3]-[3*{(31-3)/2-5}][
유효하지 않은 식입니다.
문자열을 입력하세요(/q: 종료): /q
No memory leaks detected.
Visual Leak Detector is now exiting.
C:\Users\Hotaek\Desktop\2학년 여름\DS_Review\Stack\ParenthesesChecker\Debug\ParenthesesChecker.exe(프로세스 21800개)이( 가) 종료되었습니다(코드: 0개).
이 창을 닫으려면 아무 키나 누르세요...
