괄호검사 알고리즘
프로그램에서 괄호들은 항상 쌍이 되게끔 사용되어야한다. [], (), {} ..
조건1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
조건2. 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
조건3. 서로 다른 종류의 왼쪽 괄호와 오른족 괄호 쌍은 서로를 교차하면 안된다.
{a(b}... 조건 1 위반
{a(b})... 조건 3 위반
괄호검사 알고리즘은 왼쪽 괄호가 먼저 들어가고 (스택에 push) 같은 종류의 오른쪽 괄호를 만나면 (스택에서 pop)을 하는 원리이다.
검사가 성공적이면 검사 후 스택은 비어있어야 하며 위의 조건을 만족시키지 못하면 검사가 실패한다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100 // 스택의 최대 크기
typedef int element
typedef struct { // 스택이 구조체로 정의됨
element data[MAX_STACK_SIZE];
int top;
} StackType;
//스택 초기화 함수
void init_stack(StackType *s){
s->top = -1;
}
//포화 상태 검출 함수
int is_full(StackType *s){
return (s->top == (MAX_STACK_SIZE -1)) //0~99//99면 1 아니면 0 반환
}
//공백 상태 검출 함수
int is_empty(StackType *s){
return (s->top == -1); // top이 -1이면 1 아니면 0반환
}
//삽입 함수
void push(Stacktype *s, element item){
if( is_full(s) ){
fprintf(stderr, "스택 포화 에러\n");
return;
}
else s->data[++(s->top)] = item;// top = -1이기에 배열의 0부터 시작
}
//삭제 함수
element pop(Stacktype *s){
if( is_empty(s) ){
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[(s->top)--];
}
//피크 함수
element peek(Stackype *s){
if( is_empty(s) ){
fprintf(stderr, "스택 공백 에러\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);
break;
case ')' : case ']' : case '}':
if( is_empty(&s) ) return 0;// 왼쪽 괄호 없이 오른쪽 괄호 먼저 들어가면 실패
else {
open_ch = pop(&s);
if((open_ch == '(' && ch != ')') ||
(open_ch == '{' && ch != '}') ||
(open_ch == '[' && ch != ']'))//같은 종류의 괄호가 아니면 실패
return 0;
}
break;
}
}
}
if( !is_empty(&s)) return 0;// 스택에 남아 있으면 실패
return 1; //조건이 다 만족되면 성공
}
int main(void) {
char *p = "{ A[(i+1)]=0; }"; // 포인터로 문자열의 주소를 저장
if(check_mathcing(p) == 1)
printf("%s 괄호검사성공\n", p);
else
printf("%s 괄호검사실패\n" ,p);
return 0;
}중위 표기 수식 -> 후위 표기 수식으로 변환 프로그램
a+b -> ab+
(a+b)c -> ab+c
a+bc -> abc+
스택에다 연산자를 push
주의사항 : 스택에 넣은 연산자가 다음 연산자보다 우선순위가 높으면 계산에 오류가 생김 따라서 우선순위가 높은 연산자들을 먼저 출력한 다음 처리중인 연산자를 스택에 넣어야한다.
#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_full(StackType *s){
return (s->top == (MAX_STACK_SIZE -1)) //0~99//99면 1 아니면 0 반환
}
//공백 상태 검출 함수
int is_empty(StackType *s){
return (s->top == -1); // top이 -1이면 1 아니면 0반환
}
//삽입 함수
void push(Stacktype *s, element item){
if( is_full(s) ){
fprintf(stderr, "스택 포화 에러\n");
return;
}
else s->data[++(s->top)] = item;// top = -1이기에 배열의 0부터 시작
}
//삭제 함수
element pop(Stacktype *s){
if( is_empty(s) ){
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[(s->top)--];
}
//피크 함수
element peek(Stackype *s){
if( is_empty(s) ){
fprintf(stderr, "스택 공백 에러\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(const char exp[]){
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))))
printf("%c", pop(%s));
push(&s, ch);
break;
case '(': // 왼쪽괄호
push(&s, ch);
break; // 오른쪽괄호
case ')':
top_op = pop(&s);
// 왼쪽 괄호를 만날때까지 출력
while(top_op != '(') {
printf("%c", top_op);
top_op = pop(&s);
}
break;
default:
printf("%c", ch);
break;
}
}
while (!is_empty(&s)) //스탯에 저장된 연산자들 출력
printf("%c", pop(&s));
}
int main(void) {
char *s = "(2+3)*4+9";
printf("중위 표시 수식 %s \n", s);
printf("후위 표시 수식 ");
infix-to_postfix(s);
printf("\n");
return 0;
}중위 표기식에서 후위 표기식으로 바꾸는 이유 : 컴퓨터가 계산할때 더 쉽기 때문이다.
그럼 컴퓨터가 후위 표기식을 어떻게 계산하는지 알아보자.
후위 표기식 계산
후위 표기 수식을 계산할 때에는 스택에다 피연산자를 push한다. 연산자를 만나면 스택에 있던 피연산자를 pop해서 계산을 한 결과 값을 다시 push한다. 따라서 마지막에 스택에 남겨진 피연산자가 결과값이 된다.
#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_full(StackType *s){
return (s->top == (MAX_STACK_SIZE -1)) //0~99//99면 1 아니면 0 반환
}
//공백 상태 검출 함수
int is_empty(StackType *s){
return (s->top == -1); // top이 -1이면 1 아니면 0반환
}
//삽입 함수
void push(Stacktype *s, element item){
if( is_full(s) ){
fprintf(stderr, "스택 포화 에러\n");
return;
}
else s->data[++(s->top)] = item;// top = -1이기에 배열의 0부터 시작
}
//삭제 함수
element pop(Stacktype *s){
if( is_empty(s) ){
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[(s->top)--];
}
//피크 함수
element peek(Stackype *s){
if( is_empty(s) ){
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[(s->top)];
// 후위 표기 수식 계산 함수
int eval(const char exp[]){
int op1, op2, value = 0;
int len = strlen(exp);
char ch;
Stacktype s;
init_stack(&s);
for(int i = 0; i < len; i++) {
ch = exp[i];
if( ch != '+' && ch != '-' && ch != '*' && ch != '/'){// 피연산자이면
value = ch -'0'; // char to int
push(&s, value);
}
else { //연산자이면
op2 = pop(&s); // 2개의 피연산자를 꺼내서 계산해야함
op1 = pop(&s);
switch (ch) {
case '+' : push(&s, op1+op2); break;
case '-' : push(&s, op1-op2); break;
case '*' : push(&s, op1*op2); break;
case '/' : push(&s, op1/op2); break;
}
}
}
return pop(&s);
}
int main(void)
{
int result;
printf("후위표기식은 82/3-32*+\n");
result = eval(82/3-32*+);
printf("결과값은 %d\n", result);
return 0;
}
방구석개발자