3-4강 - Evaluation of Expressions (수식의 계산)

6. Evaluation of Expressions

1) Expressions (수식)

0> 예시

- ((rear+1 == front ) || ((rear == MAX_QUEUE_SIZE-1) && !front))

- x = a/b-c+d*e-a*c

 

1> 수식의 구성 요소

- operators (연산자)
- operands (피연산자)
- parentheses (괄호)

 

2> 연산 순서에 영향을 미치는 요인 : precedence hierarchy, associativity, 괄호

- 어떤 언어든 연산자의 연산 순서를 결정하는 precedence hierarchy가 존재한다.

- precedence가 같을 경우 associativity을 따져본다. (left-to-right vs right-to-left)

- 괄호는 precedence를 변경하며, 내부 괄호부터 계산됩니다. 

 

cf> Ways of writing expression (수식 표기법)

0> 우리가 흔히 쓰는 infix 방식이 컴퓨터에서는 이 방식으로 계산하지 않는다.

1> 중위 표기법 (Infix)

- 연산자가 피연산자 사이에 있는 표기

ex> 1+2*3+1+2/2

 

2> 전위 표기법 (Prefix)

- 연산자가 피연산자 앞에 나오는 방식

ex> (infix) 1+2*3+1+2/2 -> ((1+(2*3))+(1+(2/2))) -> +((+1*(23))(+1/(22))) -> ++1*23+1/22

 

3> 후위 표기법 (Postfix)

- 연산자가 피연산자 뒤에 나오는 방식

ex> (infix) 1+2*3+(4+2)/2 -> ((1+(2*3)+((4+2)/2)))-> ((1(23)*)+((42)+2)/))+-> 123*+42+2/+

- 보통 complier는 괄호를 사용하지 않는 postfix notation을 사용한다.

 

2) Evaluation Postfix Expression

일단 'Infix -> Postfix -> calculate' 과정 중 Postfix를 연산하는 과정 먼저 다룹니다. 

1> Postfix 연산 과정 (목표 : 수식을 왼쪽에서 오른쪽으로 훑어가야 한다.)

- 연산자를 만날 때까지 피연산자를 stack에 삽입한다.

- 연산자를 만나면 연산자에 대응하는 피연산자들을 제거한다.

- 위의 피연산자와 연산자로 계산한다.

- 연산의 결과를 stack에 삽입한다.

 

2> 구현에 필요한 가정

- 연산자는 이항 연산자 +, -, *, /, %만 존재한다.

- 한 자리 숫자만 사용한다. (추후에 수식을 문자 배열로 표현할 수 있다.)

 

3> 선언할 것

- MAX_STACK_SIZE, MAX_EXPR_SIZE : stack과 연산자들 최대 저장 공간

- typedef enum {연산자} precedence : 연산자들을 enumerated type(열거 type)으로 정의

(이미 Postfix는 우선순위별로 배치가 되어서 우선순위를 고려하지 않아도 된다.) 

- int stack[MAX_STACK_SIZE] : 연산 과정들을 저장할 stack (최종 결과 하나만 0번째 index에 남게 된다.)

- char expr[MAX_EXPR_SIZE] : 연산자들을 저장할 array (사실 코드 내에서 쓸모 없다.)

- top : stack의 top / -1로 초기화

- stack의 push 함수와 pop 함수

#include <stdio.h>
#define MAX_STACK_SIZE 100 /* maximum stack size */
#define MAX_EXPR_SIZE 100 /* maximum stack size */

typedef enum {
	lparen, rparen, plus, minus, times, divide, mod, eos, operand
}precedence;

int stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE];
int top = -1;

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");
	return stack[top--];
}

 

4> input string을 token으로 만드는 함수 구현

- 현재 입력 받은 수식인 문자열 전체와 수식에서 몇 번째 문자를 입력받는지 index를 parameter로 가진다.

- 몇 번째 문자를 입력 받는지 표현하기 위해 문자열 주소값에 n을 더한 주소값을 이용 *(symbol + *n)

- 해당 문자<*(symbol + *n)>에 따라 피연산자 혹은 연산자가 switch 문으로 결정된다. 그리고 이를 return

precedence getToken(char *symbol, int *n) // 연산자 혹은 피연산자를 구분하고 이를 token으로 할당하는 함수
{
	/* get the next token, symbol is the character representation, which is returned, the
	token is represented by its enumerated value, which is returned in the function name */
	expr[++(*n)] = *(symbol+ *n);
	switch (*(symbol+ *n)) {
	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; /* no error checking, default is operand */
	}
}

 

5> postfix 수식 연산

- 현재 입력 받은 수식인 문자열 전체를 parameter로 받아서 연산하는 함수

- 선언 및 초기화

• token : 입력 받은(을) 연산자 혹은 피연산자 (getToken으로 수식에서 문자 하나씩 입력 받는다.)
• op1, op2 : 이전에 stack에 저장된 2개의 피연산자 (2개의 피연산자가 1개의 연산자로 연산이 된다.)
• n : 현재 입력 받은 수식에서 몇 번째 문자를 입력 받았는지 (push 직전에 1씩 더해지므로 -1로 초기화한다.)

- 첫 번째 loop : 입력 받은 문자(token)이 ' '이면 loop가 해제되며 함수가 종료된다.

• token이 피연산자이면 이를 stack에 push(저장) (문자니까 -> 아스키 코드에 의해 뺄셈을 하고 -> int형으로 push)
• token이 연산자라면 -> 기존에 저장된 2개의 피연산자 pop -> 현재 연산자로 2개의 피연산자와 연산 -> 결과를 stack에 push(저장)

- 위의 while문이 종료되면 모든 연산이 끝나고 그 최종 결과를 pop함수를 이용해서 return

int eval(char* symbol)
{ /* evaluate a postfix expression, expr, maintained as a global variable. '\0' is the end of the
	expression. The stack and top of the stack are global variables. getToken is used to
	return the tokentype and the character symbol. Operands are assumed to be single
	character digits */
	precedence token;
	int op1, op2;
	int n = -1; /* counter for the expression string */
	token = getToken(symbol, &n);

	while (token != eos) {
		if (token == operand)
			push(symbol[n] - '0'); /* stack insert */
		else
		{ /* remove two operands, perform operation, and return result to the stack */
			op2 = pop(); /* stack delete */
			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 */
}

 

6> main 함수

int main() {
	char Token[10] = { '6', '2', '/', '3', '-', '4', '2', '*', '+', ' ' };
	int result;
	result = eval(Token);
	
	printf("result : %d", result);
	return 0;
}

 

7> 전체 함수

#include <stdio.h>
#define MAX_STACK_SIZE 100 /* maximum stack size */
#define MAX_EXPR_SIZE 100 /* maximum stack size */

typedef enum {
	lparen, rparen, plus, minus, times, divide, mod, eos, operand
}precedence;

int stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE];
int top = -1;

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");
	return stack[top--];
}

precedence getToken(char *symbol, int *n) // 연산자 혹은 피연산자를 구분하고 이를 token으로 할당하는 함수
{
	/* get the next token, symbol is the character representation, which is returned, the
	token is represented by its enumerated value, which is returned in the function name */
	expr[++(*n)] = *(symbol+ *n);
	switch (*(symbol+ *n)) {
	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; /* no error checking, default is operand */
	}
}

int eval(char* symbol)
{ /* evaluate a postfix expression, expr, maintained as a global variable. '\0' is the end of the
	expression. The stack and top of the stack are global variables. getToken is used to
	return the tokentype and the character symbol. Operands are assumed to be single
	character digits */
	precedence token;
	int op1, op2;
	int n = -1; /* counter for the expression string */
	token = getToken(symbol, &n);

	while (token != eos) {
		if (token == operand)
			push(symbol[n] - '0'); /* stack insert */
		else
		{ /* remove two operands, perform operation, and return result to the stack */
			op2 = pop(); /* stack delete */
			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 */
}


int main() {
	char Token[10] = { '6', '2', '/', '3', '-', '4', '2', '*', '+', ' ' };
	int result;
	result = eval(Token);
	
	printf("result : %d", result);
	return 0;
}

 

교훈 

1> '7' 처럼 문자로 받은 것을 숫자로 나타내려면 '0'을 빼고 int로 나타내면 된다. by 아스키 코드

 

 

3) Infix to Postfix

1> infix에서 postfix로 만드는 알고리즘

- [1] 모두 괄호 형태로 바꾼다.

- [2] 이항 연산자를 오른쪽 괄호와 위치를 바꾼다.

- [3] 모든 괄호를 삭제한다.

 

2> 예시

 

3> 위 알고리즘의 어려움

- 2가지 과정(수식 읽고서 괄호 치고 -> 연산자를 이동)을 거치는 건 컴퓨터에게 비효율적이다.

- 피연산자는 infix나 postfix 안에서 순서가 동일하다.

- 그래서 infix를 왼쪽에서 오른쪽으로 읽어가며 postfix를 생성할 수 있다.

- 하지만 연산자의 출력 순서는 precedence에 의해 결정된다.

- 높은 우선순위의 연산자들이 먼저 출력되기 때문에 정확한 위치를 알 때까지 연산자들을 저장해두어야 한다.

- 위와 같은 특징 때문에 stack을 이용한다.

 

cf> 피연산자는 stack에 쌓지 않고 읽는 즉시 바로 출력하면 된다.

 

4> stack 구성 - 연산자에 대한 규칙

- 우선 순위가 높은 연산자가 먼저 출력되어야 한다.

- top에 있는 연산자가 incoming 연산자보다

• 우선 순위가 낮으면 stack에 incoming 연산자 삽입
• 우선 순위가 높으면 top에 있는 연산자를 즉시 출력한다. (먼저 계산할 것을 앞에 적어야 하니까)

5> stack 구성 - 괄호에 대한 규칙

- '(' 가 나타날 때까지 연산자를 stack에 쌓는다. (연산자를 출력하지 않는다.)

- '(' 가 나타나면 대응되는 ')' 가 나타날 때까지 4> 규칙에 의해 연산자를 출력한다. 

- ')' 가 나타나면 '(' 를 stack에서 삭제한다. ( ')' 는 stack에 넣지 않는다.)

6> 추가적인 문제점과 해결

- '(' 는 stack 속에 있을 때는 낮은 우선순위의 연산자처럼 작동하고 그 외에는 높은 우선 순위의 연산자처럼 작동

=> incoming일 때에는 높은 우선순위 = 괄호 밖의 연산자들이 괄호 안의 연산자보다 먼저 출력되지 않게 하려고

=> stack(top) 속에 있을 때는 낮은 우선순위 = ')'가 나올 때까지 출력하지 않으려고

- '(' 는 수식에서 발견되기만 하면 stack에 쌓이고 대응하는 ')'가 발견되면 stack에 쌓인다.

- in-stack precedence(isp) : stack 내부에서의 우선순위 ( '(' 를 0으로 제일 우선순위가 낮게 설정)

- in-coming precedence(icp) : 수식에서의 우선순위 ( '(' 를 제일 높은 우선순위로 설정)

- stack 속의 연산자 isp가 새로운 새로운 연산자의 icp보다 크거나 같을 때만 stack에서 삭제된다.

 

왼쪽 괄호가 나오면 무조건 stack에 넣어야 한다.

 

#include <stdio.h>
#include <string.h>
#define MAX_STACK_SIZE 100 /* maximum stack size */
#define MAX_EXPR_SIZE 100 /* maximum stack size */

char expr[1111];
typedef enum {
	lparen, rparen, plus, minus, times, divide, mod, eos, operand
}precedence;

precedence stack[MAX_STACK_SIZE];
/* isp and icp arrays index is value of precedence
lparen, rparen , plus, minus, times, divide, mod, eos */
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) {
	if (top >= MAX_STACK_SIZE - 1) printf("stack is full\n");
	else stack[++top] = item;
}
precedence pop() {
	if (top == -1) printf("stack is empty");
	return stack[top--];
}
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;
	}

}

precedence getToken(char *symbol, int *n) // 연산자 혹은 피연산자를 구분하고 이를 token으로 할당하는 함수
{
	/* get the next token, symbol is the character representation, which is returned, the
	token is represented by its enumerated value, which is returned in the function name */
	switch (*(symbol + *n)) {
	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; /* no error checking, default is operand */
	}
}

void postfix(void)
{ /* output the postfix of the expression. The expression string, stack, and the top are global */
	int n = 0;
	precedence token;

	stack[0] = eos;
	// 먼저 문자열 중 첫 번째 문자를 pㅅrecedence로 입력 받는다.
	// 해당 반복문은 token이 eos가 나올 때까지 반복한다.
	for (token = getToken(expr, &n); token != eos; token = getToken(expr, &n)) {
		if (token == operand) // token이 피연산자이면 바로 출력
			printf("%c", expr[n]);
		else if (token == rparen) { // token이 ')'이면 stack에서 '('이 나올 때까지 출력
			/* unstack tokens until left parenthesis */
			while (stack[top] != lparen)
				printToken(pop());
			pop();/* discard the left parenthesis */
		}
		else { // 연산자이거나 '('이면 
			// top에 있는 연산자의 우선 순위가 높으면 출력
			// stack의 연산자와 incoming 연산자의 우선 순위를 다르게 처리한다.
			/* remove and print symbols whose isp is greater
			than or equal to the current token’s icp */
			while (isp[stack[top]] >= icp[token])
				printToken(pop()); 
			// top에 있는 연산자가 incoming 연산자보다 우선순위가 낮아질 때까지 출력
			push(token);
		}
		n++;
	}
	while ((token = pop()) != eos)
		printToken(token);
	printf("\n");
}

int main() {
	scanf("%s", expr);
	postfix();
	printf("%s\n", expr);
	return 0;
}