BOJ 1935 : 후위 표기식2

알고리즘 문제 전체 링크

삼성 C형 전체 링크

 

https://www.acmicpc.net/problem/1935

 

참고

- 스택

- 괄호

- 후위 표기식 (중위 표기식을 후위 표기식으로 변경하기)

- 중위 표기식

 

 

후위 표기식의 연산은 매우 간단하다.

다음의 규칙대로 구현하면 된다.

 

1. 숫자는 stack에 넣는다.

2. 연산자가 나오면 stack에서 숫자 두 개를 빼고 연산한 후, 결과를 다시 스택에 집어 넣는다.

  이때, 처음 나온 숫자가 뒤에 있는 연산이 된다. ( - 연산자를 만나고 a가 먼저 나온 후 b가 나온다면 b - a가 된다.)

3. 위 과정을 모두 반복하고 스택에 남아 있는 숫자가 최종 연산 결과가 된다.

 

숫자(알파벳)와 연산자를 구분하기 위해 table 배열을 사용하여서 위의 내용을 구현한 결과는 아래와 같다.

#include <stdio.h>

#define OPERATOR (1)
#define ALPHABET (2)

int N;
char formula[110];
int number['Z' + 1];

int main()
{
	int table[300] = { 0 };

	scanf("%d %s", &N, formula);

	for (int i = 0; i < N; i++) scanf("%d", &number['A' + i]);
	
	for (int i = 'A'; i <= 'Z'; i++) table[i] = ALPHABET;

	table['+'] = table['-'] = table['*'] = table['/'] = OPERATOR;

	double stack[110];
	int sp = 0;

	double answer = 0;
	for (int i = 0; formula[i]; i++)
	{
		// 1. 숫자는 stack에 넣는다.
		if (table[formula[i]] == ALPHABET) stack[sp++] = (double)number[formula[i]];
		else // 2. 연산자가 나오면
		{
			// stack에서 숫자 두 개를 빼고 연산한 후, 
			double a = stack[--sp];
			double b = stack[--sp];
			double c;

			char op = formula[i];

			// 뒤에 나온 숫자를 먼저 계산한다.
			if (op == '+') c = b + a;
			else if (op == '-') c = b - a;
			else if (op == '*') c = b * a;
			else //if (op == '/')
				c = b / a;

			// 결과를 다시 스택에 집어 넣는다.
			stack[sp++] = c;
		}
	}

	// 3. 위 과정을 모두 반복하고 스택에 남아 있는 숫자가 최종 연산 결과가 된다.
	printf("%.2f\n", stack[sp - 1]);

	return 0;
}