chapter 3-2 : Stack & Queue (Infix(중위 표기법), Postfix(후위 표기법))

컴파일러의 표기법 (후위 표기법 표현)

중위 표기법(Infix)	전위 표기법(Prefix)	후위 표기법(Postfix)
ex) 2 + 3 * 4	ex) + 2 * 3 4	ex 2 3 4 * +
ex) a * b + 5	ex) + * a b 5	ex) a b * 5 +
ex) (1 + 2) * 7	ex) * + 1 2 7	ex) 1 2 + 7 *

우리는 일반적으로 중위 표기법을 사용해서 문제를 해결합니다.

그렇지만 컴퓨터는 후위 표기법으로 수식을 인식하고 계산합니다.

그래서 컴퓨터의 입장을 체험하고자 컴퓨터의 편의를 위해 우리가 미리 후위표기법 표현해주면 더 빠른 연산이 가능합니다.

이를 위해 우리는 stack 자료구조를 활용합니다.

배열 "8 2 / 3 -" 배열을 입력받았다고 가정하면 아래와 같은 과정이 실행되어야 합니다.

stack 활용 연산

위의 그림에서 배열을 문자열로 받아줄것입니다. 그 다음 연산자와 피연산자를 구별해 

다시 정수형 stack에 다시 넣어 줍니다.

#define MAX_STACK_SIZE 100 //stack의 최대저장공간
#define MAX_EXPR_SIZE 100 //연산자들의 최대저장 공간
typedef enum { //연산자들을 정의
	lparen, rparen, plus, minus, times, divide, mod, eos, operand
}precedence;
int stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE] = { '6', '2', '/', '3', '-', '4', '2', '*', '+', ' ' };
int top = -1;

연산자들은 enum 열거형 type로 설정해 구조체형 변수 predence로 선언해 어떤 연산자가 들어오는지 구별할 것입니다.

stack에는 연산의 결과값만이 들어가고 문자열 expr에는 후위 표기법 수식이 들어옵니다.

변수 top은 stack를 가리키는 변수입니다.

---

void push(int item) {
	if (top >= MAX_STACK_SIZE - 1)
		printf("stack is Full\n");
	else stack[++top] = item;
}
int pop() {
	if (top == -1)
		printf("stack is Empty\n");
	return stack[top--];
}

push 함수와 pop 함수입니다.

---

precedence getToken(char* symbol, int* n) {
	*symbol = expr[(*n)++];
	switch (*symbol) {
	case '(':return lparen;
	case ')':return rparen;
	case '+':return plus;
	case '-':return minus;
	case '/':return divide;
	case '*':return times;
	case '%':return mod;
	case ' ':return eos;
	default : return operand; //기본값
	}
}

문자열 expr에서 문자 1개(symbol)를 읽어와서 이 문자가 연산자인지, 피연산자 인지 구별해주는 함수입니다.

포인터 변수 n은 문자열 expr의 인덱스 위치를 가리키는 변수입니다.

만약 피연산자가 들어오면 기본값(default)경우 이므로 oprand를 출력합니다.

---

int eval() {
	precedence token;
	int op1, op2;
	char symbol;
	int n = 0; //스트링 1개씩 읽어오는 n
	token = getToken(&symbol, &n);

	while (token != eos) {
		if (token == operand)
			push((symbol - '0'));
		else {
			op2 = pop();
			op1 = pop();
			switch (token) {
			case plus: push(op1 + op2); break;
			case minus: push(op1 - op2); break;
			case times: push(op1 * op2); break;
			case divide:push(op1 / op2); break;
			case mod: push(op1 % op2); 
			}
		}
		token = getToken(&symbol, &n); //그 다음 token 초기화
	}
	return pop(); //return result
}

변수 op1 과 op2는 피연산자를 받을 변수입니다. (즉, 숫자) 

변수 n은 아까 getToken 함수에서 봤듯이 문자열 expr의 인덱스 위치를 가리키는 변수입니다.

while 문에서 eos는 문자열의 끝입니다. getToken 함수에서 출력받은것이 token변수에 들어오므로

token 변수가 eos만 안받으면 while문은 실행됩니다.

if문에서 token이 숫자(operand)이면 stack에 넣어줍니다.

연산자라면 stack에 쌓여있는 숫자들을 pop함수를 통해 먼저 op2에 옮기고 그 다음 op1에 옮깁니다.

switch 함수를 통해 해당사항에 따라서 case문을 수행해 줍니다.

다 끝나고 다음 token을 받아주고 while문은 계속 반복됩니다.

while문이 다 끝나면 stack에는 완전히 계산된 숫자만 있으므로 pop을 return해 줍니다.

---

전체 코드입니다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define MAX_STACK_SIZE 100 //stack의 최대저장공간
#define MAX_EXPR_SIZE 100 //연산자들의 최대저장 공간
typedef enum { //연산자들을 정의
	lparen, rparen, plus, minus, times, divide, mod, eos, operand
}precedence;
int stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE] = { '6', '2', '/', '3', '-', '4', '2', '*', '+', ' ' };//연사자들을 저장할 array
int top = -1;
void push(int item);
int pop();
precedence getToken(char* symbol, int* n);
int eval();
int main() {
	int result;
	result = eval(expr);
	printf("result : %d", result);
	return 0;
}
precedence getToken(char* symbol, int* n) {
	*symbol = expr[(*n)++];
	switch (*symbol) {
	case '(':return lparen;
	case ')':return rparen;
	case '+':return plus;
	case '-':return minus;
	case '/':return divide;
	case '*':return times;
	case '%':return mod;
	case ' ':return eos;
	default : return operand; //기본값
	}
}
int eval() {
	precedence token;
	int op1, op2;
	char symbol;
	int n = 0; //스트링 1개씩 읽어오는 n
	token = getToken(&symbol, &n);

	while (token != eos) {
		if (token == operand)
			push((symbol - '0'));
		else {
			op2 = pop();
			op1 = pop();
			switch (token) {
			case plus: push(op1 + op2); break;
			case minus: push(op1 - op2); break;
			case times: push(op1 * op2); break;
			case divide:push(op1 / op2); break;
			case mod: push(op1 % op2); 
			}
		}
		token = getToken(&symbol, &n);
	}
	return pop(); //return result
}
void push(int item) {
	if (top >= MAX_STACK_SIZE - 1)
		printf("stack is Full\n");
	else stack[++top] = item;
}
int pop() {
	if (top == -1)
		printf("stack is Empty\n");
	return stack[top--];
}

이러한 알고리즘은 괄호를 처리하는데에는 불가능합니다.

---

Infix To Postfix (중위 표기법에서 후위 표기법으로 바꾸기)

이제 우리가 일반적으로 쓰는 중위 표기법에서 후위 표기법으로 바꾸는

알고리즘을 짜겠습니다.

우리가 중위 표기법으로 수식을 입력하면 후위 표기법으로 바꾸어야 하기

때문에

괄호, +, -, *, /, % 등 연산자에 대한 순위가 있어야 합니다.

따라서 숫자는 그대로 출력 해주고 

연산자들은 stack에 연산자의 순위를 고려해 따로 넣어주면됩니다.

 

 

 

 

 

 

 

typedef enum { //연산자들을 정의
	lparen, rparen, plus, minus, times, divide, mod, eos, operand
}precedence;
precedence stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE];
int isp[] = { 0,19,12,12,13,13,13,0 };
int icp[] = { 20,19,12,12,13,13,13,0 };
int top = 0;

precedence   type는 enum(열거) 형이므로 아까전에 있는 것과 똑같습니다.

여기서 중요한게 isp배열과 icp 배열인데 

isp배열의 0번째 인덱스와 icp배열의 0번째 인덱스만 다르고 나머지는 모두 동일합니다.

왜냐하면 '(' 괄호 때문인데요 우선순위로 따지면 '(' 는 20입니다. 

나중에 isp[stack[top]] >= icp[token] 라는 코드를 실행하는데 이때, stack안에 있는 '('를 우선순위를 낮추기 위함입니다.

따라서 스택안의 '('의 우선순위가 0으로 제일 낮으므로 icp 배열에 있는 연산자들은 stack에 들어갈 수 있는 것입니다.

top은 0으로 초기화 해주는데 나중에 stack[0]을 eos로 초기화 해주기 때문입니다.

void postfix() {
	int n = 0; //문자열 expr의 인덱스 위치를 가리키는 변수
	precedence token; //expr의 출력값을 임의로 저장할 변수
	char symbol;

	stack[0] = eos; //스택에 eos넣음 따라서 top은 0이 되어야함
	
	for (token = getToken(&symbol, &n); token != eos; token = getToken(&symbol, &n)) {
		if (token == operand) //token이 피연산자일때
			printf("%c", symbol);
		else if (token == rparen) { //token이 ')' 일떄
			while (stack[top] != lparen)
				printToken(pop());
			pop();
		}
		else { //token이 연산자 일때
			while (isp[stack[top]] >= icp[token]) //stack안에 있는 연산자와 우선순위 비교
				printToken(pop());
			push(token);
		}
	}
	while ((token = pop()) != eos) //스택안에 남아있는 연산자 출력
		printToken(token);
	printf("\n");
}

중위 표기법은 후위 표기법으로 변환해주는 함수 입니다. 

for문에서  token을 계속해서 문자열 expr에서 입력받아 문자열의 끝 eos를 받을때까지 반복합니다.

if 문에서는 피연산자(숫자)를 받을 경우 stack에 넣지 않고 그냥 그대로 출력해줍니다.

else if 문에서는 token이 ')' 일떄 괄호안에 있는 수식들이 우선순위 이므로 stack에서 '(' 가 나올때 까지

그 사이에 있는 모든 연산자들을 출력해줍니다. 다 출력해주고 스택에 남아있는 '(' 를 pop을 통해 제거해줍니다.

else문에서는 while 문을 통해 stack안에 있는 연산자와 들어올 연산자의 우선순위를 비교해 push함수를 통해 

넣어 줍니다.

마지막은 token이 eos에 도달할때 까지 남아있는 stack의 연산자를 모두 출력해줍니다.

---

전체코드입니다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define MAX_STACK_SIZE 100 //stack의 최대저장공간
#define MAX_EXPR_SIZE 100 //연산자들의 최대저장 공간
typedef enum { //연산자들을 정의
	lparen, rparen, plus, minus, times, divide, mod, eos, operand
}precedence;
precedence stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE];
int isp[] = { 0,19,12,12,13,13,13,0 };
int icp[] = { 20,19,12,12,13,13,13,0 };
int top = 0;
void push(precedence item);
precedence pop();
precedence getToken(char* symbol, int* n);
void printToken(precedence token); //연산자 출력 함수
void postfix();
int main() {
	scanf("%s", &expr);
	postfix();
	return 0;
}
precedence getToken(char* symbol, int* n) {
	*symbol = expr[(*n)++];
	switch (*symbol) {
	case '(':return lparen;
	case ')':return rparen;
	case '+':return plus;
	case '-':return minus;
	case '/':return divide;
	case '*':return times;
	case '%':return mod;
	case '\0':return eos;
	default: return operand; //기본값
	}
}
void printToken(precedence token) { //연산자 출력함수
	switch (token) {
	case lparen:printf("("); break;
	case rparen:printf(")"); break;
	case plus:printf("+"); break;
	case minus:printf("-"); break;
	case divide:printf("/"); break;
	case times:printf("*"); break;
	case mod:printf("%%"); break;
	case eos:printf("\0"); break;
	}
}
void postfix() {
	int n = 0;
	precedence token;
	char symbol;

	stack[0] = eos;
	
	for (token = getToken(&symbol, &n); token != eos; token = getToken(&symbol, &n)) {
		if (token == operand)
			printf("%c", symbol);
		else if (token == rparen) {
			while (stack[top] != lparen)
				printToken(pop());
			pop();
		}
		else {
			while (isp[stack[top]] >= icp[token])
				printToken(pop());
			push(token);
		}
	}
	while ((token = pop()) != eos)
		printToken(token);
	printf("\n");
}
void push(precedence item) {
	if (top >= MAX_STACK_SIZE - 1)
		printf("stack is Full\n");
	else stack[++top] = item;
}
precedence pop() {
	if (top == -1)
		printf("stack is Empty\n");
	return stack[top--];
}