스택 괄호검사 프로그램

스택을 이용하여 괄호를 검사하는 프로그램을 확인해보겠습니다. 괄호는 "[, ]", "{, }", "(, )"등 세가지를 사용하여 서로쌍인지 검사하겠습니다.

 

소스 코드

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_STACK_SIZE 100 typedef char element; typedef struct {     element data[MAX_STACK_SIZE];     int top; } StackType; // 스택 초기화 함수 void init_stack(StackType* s) {     s->top = -1; } // 공백 상태 검출 함수 int is_empty(StackType* s) {     return (s->top == -1); } // 포화 상태 검출 함수 int is_full(StackType* s) {     return (s->top==(MAX_STACK_SIZE-1)); } // 삽입함수 void push(StackType* s, element item) {     if (is_full(s)) {         printf("스택 포화 에러\n");         return;     }     else s->data[++(s->top)] = item; } // 삭제함수 element pop(StackType* s) {     if (is_empty(s)) {         printf("스택 공백 에러\n");         exit(1);     }     else return s->data[(s->top)--]; } // 피크함수 element peek(StackType* s) {     if (is_empty(s)) {         printf("스택 공백 에러\n");         exit(1);     }     else return s->data[s->top]; }

//괄호 검사  int check_matching(const char* in)  {      StackType s;      char ch, open_ch;      int i, n = strlen(in);      init_stack(&s);      for (i = 0; i < n; i++) {          ch = in[i];          switch (ch) {          case '(':          case '[':          case '{':              push(&s, ch);              printf("삽입 : %c\n", ch);              break;          case ')':          case ']':          case '}':              if (is_empty(&s)) //스택이 비어 있으면 오류 아니면 pop()실행                  return 0;              else              {                  open_ch = pop(&s);                  printf("삭제 : %c\n", ch);                  if ((open_ch == '(') && ch != ')' || (open_ch == '[') && ch != ']' || (open_ch == '{') && ch != '}')                      return 0;                   }                   break;              }      }      if (!is_empty(&s)) //스택에 남아있으면 오류          return 0;      return 1;  }  int main(void)  {      const char* p = "({}[])";      if (check_matching(p) == 1)          printf("%s 괄호검사 성공\n", p);      else          printf("%s 괄호검사 실패\n", p);  }

 

스택을 이용하여 수식 계산

수식을 표현하는 방법에는 중위, 후위, 전위로 3가지 방법이 있습니다. 사람이 사용하는 수식은 중위표기법을 사용합니다.

 

중위 표기법	후위 표기법	전위 표기법
2+5*4	254*+	+2*54
(3+4)*5	34+5*	*+345

 

중위  표기로 (3+4)*5의 경우 괄호는 더하기 연산이 곱하기 연산보다 먼저 수행되어야 합니다. 이것을 후위 표기로 34+5*로 표현되어 괄호를 쓰지 않고도 우선 계산하여야 수식을 표현 할 수 있습니다. 이처럼 우선 순위도 생각할 필요 없이 왼쪽에서 오른쪽으로 읽어들이면서 연산을 실행하면 됩니다.

스택을 이용하여 계산해 보도록 하겠습니다.

중위 표기식을 후위표기법으로 바꾸기

중위 표기 수식을 후위 표기 수식으로 변환하기 위하여 입력 수식을 왼쪽에서 오른쪽으로 읽어들인다. 왼쪽에서 읽어들이면서 피연산자는 후위 표기 수식에 출려하고 연산자는 스택에저장한다. 왜냐하면 후위 표기 수식에서는 피연산자가 위에 나오기 때문이다. 따라서 적절한 위치를 찾을 때가지 출력을 보류하여 한다. 예를 들어 "a+b"라는 수식이 있으면 a는 그대로 출력되고 +는 스택에 저장하고 b는 출력하고 최종적으로 스택에 저장된 +를 출력하면 "ab+"가 된다. 또 다른 예를 보면 "a+b*c"에서 보면, a, b, c는 그대로 출력되고 +, *는 스택에 저장한다. 문제는 +연산자와 *연산자 중에서 어떤 것이 먼저 출력되어야 할까? 기본적으로 가장 나중에 삽입된 연산자가 가장 먼저 출력되어야 한다. 따라서 연산자들은 스택에 저장되는 것이 타당하다. 왜냐하면 스택은 가장 늦게 입력된 것이 가장 먼저 출력되는 구조이기 때문이다. 따라서 +연산자와 *연산자는 스택에 저장되었다가 *연산자가 먼저 출력되고 +연산자가 나중에 출력되어 "abc*+" 가 된다.

스택을 이용하여 수식을 계산하는 프로그램

#include <stdio.h> #include <stdlib.h> #include <string.h> // ===== 스택 코드의 시작 =====  #define MAX_STACK_SIZE 100 typedef char element; typedef struct {     element data[MAX_STACK_SIZE];     int top; } StackType; //수식을 계산할때 사용 typedef struct {     int data[MAX_STACK_SIZE];     int top; } StackRet; // 스택 초기화 함수 void init_stack(StackType* s) {     s->top = -1; } // 공백 상태 검출 함수 int is_empty(StackType* s) {     return (s->top == -1); } // 포화 상태 검출 함수 int is_full(StackType* s) {     return (s->top == (MAX_STACK_SIZE - 1)); } // 삽입함수 void push(StackType* s, element item) {     if (is_full(s)) {         printf("스택 포화 에러\n");         return;     }     else s->data[++(s->top)] = item; } // 삭제함수 element pop(StackType* s) {     if (is_empty(s)) {         printf("스택 공백 에러\n");         exit(1);     }     else return s->data[(s->top)--]; } // 피크함수 element peek(StackType* s) {     if (is_empty(s)) {         printf("스택 공백 에러\n");         exit(1);     }     else return s->data[s->top]; } //연산자 우선 순위 int prec(char op) {     switch (op) {     case '(':     case ')':         return 0;     case '+':     case '-':         return 1;     case '*':     case '/':         return 2;     } return -1; } //중위 표기 수식 -> 후위 표기 수식 void infix_to_postfix(char exp[], char ret[], int cnt) {     int i = 0;     char ch, top_op;     int len = strlen(exp);     StackType s;     init_stack(&s);     for (i = 0; i < len; i++) {         ch = exp[i];         switch (ch) {//연산자         case'+':         case'-':         case'*':         case'/': //스택에 있는 연산자의 우선순위가 더 크거나 같으면 출력             while (!is_empty(&s) && (prec(ch) <= prec(peek(&s)))) {                 ret[cnt++] = ch;                 printf("%c", pop(&s));             }             push(&s, ch);             break;         case'('://왼쪽 괄호             push(&s, ch);             break;         case')': //오른쪽 괄호             top_op = pop(&s);             while (top_op != '(') {   //왼쪽 괄호를 만날때까지 출력                 ret[cnt++] = top_op;                 printf("%c", top_op);                 top_op = pop(&s);             }             break;         default: //피연산자             ret[cnt++] = ch;             printf("%c", ch);             break;         }     }     while (!is_empty(&s)) { // 스택에 저장된 연산자들 출력         top_op = pop(&s);         ret[cnt++] = top_op;         printf("%c", top_op);     }     ret[cnt] = NULL; }

//########## 수식계산 스택 ############## // 스택 초기화 함수 void init_stack_int(StackRet* s) {     s->top = -1; } // 공백 상태 검출 함수 int is_empty_int(StackRet* s) {     return (s->top == -1); } // 포화 상태 검출 함수 int is_full_int(StackRet* s) {     return (s->top == (MAX_STACK_SIZE - 1)); } // 삽입함수 void push_int(StackRet* s, int item) {     if (is_full_int(s)) {         printf("스택 포화 에러\n");         return;     }     else s->data[++(s->top)] = item; } // 삭제함수 int pop_int(StackRet* s) {     if (is_empty_int(s)) {          printf("스택 공백 에러\n");          exit(1);     }     else return s->data[(s->top)--]; } // 피크함수 int peek_int(StackRet* s) {     if (is_empty_int(s)) {         printf("스택 공백 에러\n");         exit(1);     }     else return s->data[s->top]; } //######################################## int postfix_ret(char exp[]) {     int i = 0, n_ret=0, num1, num2, top_op1, top_op2;     char ch;     int len = strlen(exp);     StackRet s;     init_stack_int(&s);     for (i = 0; i < len; i++) {         ch = exp[i];         switch (ch) {//연산자         case'+':         case'-':         case'*':         case'/':             while (!is_empty_int(&s)) {                 top_op1 = pop_int(&s);                 num2 = top_op1;                 top_op2 = pop_int(&s);                 num1 = top_op2;                 switch (ch) {                 case'+':                     n_ret = num1 + num2;                     break;                 case'-':                     n_ret = num1 - num2;                     break;                 case'*':                     n_ret = num1 * num2;                     break;                 case'/':                     n_ret = num1 / num2;                     break;                 }             }             push_int(&s, n_ret);             break;         default: //피연산자             push_int(&s, ch-'0');             break;         }     }     return n_ret; } int main(void) {     char arr[MAX_STACK_SIZE];     int cnt=0;       char s[100] = "(9-3)*4";     printf("중위표시수식 %s \n", s);     printf("후위표시수식 ");     infix_to_postfix(s, arr, cnt);     printf("\n");     printf("후위표기수식 배열 : %s\n", arr);     printf("########################\n");     printf("%d\n", postfix_ret(arr));     return 0; }