참고
- 스택
- 괄호
- 후위 표기식
중위 표기법 연산은 아래와 같다.
1. 숫자를 만나면 현재 숫자(cur)를 저장해둔다.
2. +, - 연산자가 나오면 temp에 현재의 숫자를 곱한다. (temp는 1로 초기화)
3. 그리고 result에 temp를 더한다.
4. *, / 가 나오면 temp에 값을 누적한다.
5. 이후 +, - 연산자가 나오면 2 ~ 3을 실행한다.
6. 모두 종료 후 남은 연산 실행
이때 괄호를 만나면 닫힌 괄호까지를 먼저 계산하고 temp로 변경한다.
그리고 괄호 연산이 끝난 경우는 다음 연산을 위해 cur = 1로 초기화 해야 한다.
괄호 내에서는 다시 중위 표기식이 될 것이기 때문에 위의 방법을 그대로 적용하여 재귀 함수로 만든다.
괄호가 있는 경우의 규칙을 적용하여 아래의 중위 표기식을 연산해보자.
정수 연산을 피하기 위해 나누기 / 연산은 하지 않는다. (중위 표기식 설명에서 operator는 항상 * 가 되므로 생략)
4 + ( 2 + ( 6 * 4 - 7 * 4 ) + 5 ) - 3
= 4 + ( 2 + ( -4 ) + 5) - 3
= 4 + ( 3 ) - 3
= 4
계산을 해본 결과 4가 나온다.
규칙대로 연산해서 4가 나오는지 확인해보자.
현재 숫자 cur = 0, 임시 저장 변수 temp = 1, 최종 결과 result는 0으로 초기화한다.
현재 숫자를 4로 갱신한다.
+ 를 만났으므로, temp에 현재 숫자를 곱하고 result에 누적한다.
그리고 + 연산은 temp를 1로 초기화한다.
첫 번째 괄호를 만났다.
이 괄호와 짝이 되는 괄호까지를 다시 연산해서 temp로 변경해야 한다.
이 경우 새로운 중위 표현식을 계산하는 함수가 호출되므로,
해당 함수 내의 스택에 cur, temp, result가 초기화된다.
2를 만났으므로 cur을 2로 바꾼다.
+ 를 만났으므로 temp에 현재 숫자를 곱하고, result에 누적, temp는 1로 초기화한다.
두 번째 괄호를 만났다.
이 괄호와 짝이 되는 괄호까지를 또 다시 연산해서 temp로 변경해야 한다.
이 경우도 새로운 중위 표현식을 계산하는 함수가 호출되므로,
해당 함수 내의 스택에 cur, temp, result가 초기화된다.
현재 숫자를 6으로 변경한다.
* 연산을 만났으므로 temp에 cur을 곱한다.
현재 숫자를 4로 변경한다.
- 연산을 만났으므로 temp에 cur을 곱하고 result에 누적한다.
그리고 - 연산은 temp를 -1로 초기화한다.
현재 숫자를 7로 갱신한다.
* 연산을 만났으므로 temp에 cur을 곱한다.
현재 숫자를 4로 갱신한다.
두 번째 괄호가 종료되었으므로 남아있는 연산을 처리한다.
두 번째 괄호의 중위 표기식은 -4가 된다.
첫 번째 괄호로 다시 돌아가면 아래와 같이 괄호가 통째로 temp = -4로 교체된다.
괄호 연산이 종료되면 cur을 1로 초기화해야 한다.
cur을 1로 초기화했기 때문에 다음 연산자를 만났을 때 기존의 규칙을 그대로 적용해서 result를 갱신할 수 있다.
cur을 1로 초기화하지 않으면 이전에 있던 cur = 2가 곱해져서 엉뚱한 값이 계산되기 때문이다.
현재 숫자를 5로 바꾼다.
첫 번째 괄호가 종료되었다.
남아있는 연산을 하면 3이 된다.
결국 (두 번째가 포함된) 첫 번째 괄호의 연산 결과는 3이므로 식이 아래와 같이 변경된다.
temp = 3으로 교체된다.
괄호 연산이 종료되었으므로 cur을 1로 바꾼다.
- 를 만났으므로 temp에 cur을 곱하고 result에 누적한다.
- 연산이므로 temp = -1로 초기화한다.
현재 숫자를 3으로 변경한다.
for 문이 종료되었으므로 남아있는 연산을 처리한다.
4 + ( 2 + ( 6 * 4 - 7 * 4 ) + 5 ) - 3 = 4 가 나오게 되었다.
위와 같은 방법으로 다음 예시들도 똑같이 계산해보면 아래와 같이 답이 나온다.
4 + ( 2 + ( 6 * 4 - 7 * 4 ) + 5 ) - 3 = 4
1 + ( 5 - 7 - 1 ) * ( 3 - 7 + ( 3 - 4 + 1 ) ) - 5 = 8
4 * 1 * 7 + ( 6 * 6 - 7 * 7 + 3 * 5 - 4 * 3 * 7 - 4 - 9 - 2 - 9 ) = -78
6 * 6 - 2 - 9 * 7 * 3 - 6 + 6 - 7 + 9 + ( 8 * 4 - 6 + 8 - 7 * 9 ) = -182
8 - 3 + 8 - 6 - 4 + 2 - 4 * 1 + 4 - 2 * 5 - 6 * 2 * 7 * 8 - 3 = -680
4 + ( 1 + 2 * 7 - 7 - 5 + ( 7 - 2 + 3 - 5 - 4 + 6 * 4 - 8 - 7 * 4 ) ) = -6
7 + 5 * 5 * 2 * 8 - 5 * 6 * 7 + ( 9 - 7 - 3 * 4 - 6 + 2 * 8 + ( 8 ) ) = 205
2 * 8 + 3 + 5 + 4 * 7 - 2 - 8 * 5 - 3 - 7 - 9 * 8 - 8 + ( 7 - 4 ) = -77
3 - 9 + 6 + 6 + 4 - 2 - 3 - 3 - 6 + ( 2 + ( 6 - 2 + 4 + 4 - 3 * 6 ) ) = -8
8 + 5 + 3 + ( 3 - 1 * 8 + ( 3 * 9 * 7 - 4 * 7 * 1 + 5 - 1 + ( 5 - 8 ) ) ) = 173구현
구현의 편의상 다음과 같은 중위 표기법이 주어진다고 가정한다.
1. 중위 표기법에서 나눗셈 연산이 들어오지 않는다.
2. 모든 숫자는 1 ~ 9 사이로만 주어진다.
ㄴ 10 이상의 숫자라면 string을 parsing하여 숫자로 만드는 과정을 추가한다.
정답을 검증하기 위해 수식과 답을 아래와 같이 저장한다.
char formula[10][100]
= {
"4 + ( 2 + ( 6 * 4 - 7 * 4 ) + 5 ) - 3", // = 4
"1 + ( 5 - 7 - 1 ) * ( 3 - 7 + ( 3 - 4 + 1 ) ) - 5", // = 8
"4 * 1 * 7 + ( 6 * 6 - 7 * 7 + 3 * 5 - 4 * 3 * 7 - 4 - 9 - 2 - 9 )", // = -78
"6 * 6 - 2 - 9 * 7 * 3 - 6 + 6 - 7 + 9 + ( 8 * 4 - 6 + 8 - 7 * 9 )", // = -182
"8 - 3 + 8 - 6 - 4 + 2 - 4 * 1 + 4 - 2 * 5 - 6 * 2 * 7 * 8 - 3", // = -680
"4 + ( 1 + 2 * 7 - 7 - 5 + ( 7 - 2 + 3 - 5 - 4 + 6 * 4 - 8 - 7 * 4 ) )", // = -6
"7 + 5 * 5 * 2 * 8 - 5 * 6 * 7 + ( 9 - 7 - 3 * 4 - 6 + 2 * 8 + ( 8 ) )", // = 205
"2 * 8 + 3 + 5 + 4 * 7 - 2 - 8 * 5 - 3 - 7 - 9 * 8 - 8 + ( 7 - 4 )", // = -77
"3 - 9 + 6 + 6 + 4 - 2 - 3 - 3 - 6 + ( 2 + ( 6 - 2 + 4 + 4 - 3 * 6 ) )", // = -8
"8 + 5 + 3 + ( 3 - 1 * 8 + ( 3 * 9 * 7 - 4 * 7 * 1 + 5 - 1 + ( 5 - 8 ) ) )", // = 173
};
int answer[] = { 4, 8, -78, -182, -680, -6, 205, -77, -8, 173 };
연산을 편하게 하기 위해 '0' ~ '9'는 0 ~ 9로 바꾼다.
그리고 열린 괄호 ( 를 만나면 스택에 추가하고 닫힌 괄호 ) 를 만나면 pair에 기록하고 스택에서 제거한다.
(참고: Brainf**k 인터프리터)
for (int i = 0; testFormula[i]; i++)
{
if ('0' <= testFormula[i] && testFormula[i] <= '9') testFormula[i] -= '0';
else if (testFormula[i] == '(') stack[sp++] = i;
else if (testFormula[i] == ')')
{
pair[i] = stack[sp - 1];
pair[stack[sp - 1]] = i;
sp--;
}
}
formula에 대한 정보를 모두 저장하였다면 중위 표기법을 계산한다.
int ret = calculateInfix(testFormula, 0, len);
char ox = (ret == answer[tc]) ? 'o' : 'x';
printf("[tc :%02d]\ncal: %d\nanswer : %d (%c)\n\n", tc + 1, ret, answer[tc], ox);
위에서 설명한 규칙을 그대로 적용하면 아래와 같이 구현할 수 있다.
int calculateInfix(char formula[], int start, int end)
{
int result = 0;
int temp = 1;
int cur = 0;
for (int i = start; i < end; i++)
{
if (formula[i] == ' ') continue;
// 1. 숫자를 만나면 현재 숫자(cur)를 저장해둔다.
if (0 <= formula[i] && formula[i] <= 9)
{
cur = formula[i];
}
// 괄호를 만나면 닫힌 괄호까지 계산해서 temp로 변경, cur은 1로 초기화
else if (formula[i] == '(')
{
int bracket = calculateInfix(formula, i + 1, pair[i]);
temp *= bracket;
i = pair[i];
cur = 1;
}
// temp에 누적, result에 누적, temp 초기화
else if (formula[i] == '+' || formula[i] == '-')
{
temp *= cur;
result = result + temp;
temp = (formula[i] == '+') ? 1 : -1;
}
// temp에 누적
else if (formula[i] == '*')
{
temp *= cur;
}
}
temp *= cur;
result = result + temp;
return result;
}
전체 코드는 다음과 같다.
#include <stdio.h>
int stack[100];
int sp;
int pair[100];
int calculateInfix(char formula[], int start, int end)
{
int result = 0;
int temp = 1;
int cur = 0;
for (int i = start; i < end; i++)
{
if (formula[i] == ' ') continue;
// 1. 숫자를 만나면 현재 숫자(cur)를 저장해둔다.
if (0 <= formula[i] && formula[i] <= 9)
{
cur = formula[i];
}
// 괄호를 만나면 닫힌 괄호까지 계산해서 temp로 변경, cur은 1로 초기화
else if (formula[i] == '(')
{
int bracket = calculateInfix(formula, i + 1, pair[i]);
temp *= bracket;
i = pair[i];
cur = 1;
}
// temp에 누적, result에 누적, temp 초기화
else if (formula[i] == '+' || formula[i] == '-')
{
temp *= cur;
result = result + temp;
temp = (formula[i] == '+') ? 1 : -1;
}
// temp에 누적
else if (formula[i] == '*')
{
temp *= cur;
}
}
temp *= cur;
result = result + temp;
return result;
}
int main(void)
{
char formula[10][100]
= {
"4 + ( 2 + ( 6 * 4 - 7 * 4 ) + 5 ) - 3", // = 4
"1 + ( 5 - 7 - 1 ) * ( 3 - 7 + ( 3 - 4 + 1 ) ) - 5", // = 8
"4 * 1 * 7 + ( 6 * 6 - 7 * 7 + 3 * 5 - 4 * 3 * 7 - 4 - 9 - 2 - 9 )", // = -78
"6 * 6 - 2 - 9 * 7 * 3 - 6 + 6 - 7 + 9 + ( 8 * 4 - 6 + 8 - 7 * 9 )", // = -182
"8 - 3 + 8 - 6 - 4 + 2 - 4 * 1 + 4 - 2 * 5 - 6 * 2 * 7 * 8 - 3", // = -680
"4 + ( 1 + 2 * 7 - 7 - 5 + ( 7 - 2 + 3 - 5 - 4 + 6 * 4 - 8 - 7 * 4 ) )", // = -6
"7 + 5 * 5 * 2 * 8 - 5 * 6 * 7 + ( 9 - 7 - 3 * 4 - 6 + 2 * 8 + ( 8 ) )", // = 205
"2 * 8 + 3 + 5 + 4 * 7 - 2 - 8 * 5 - 3 - 7 - 9 * 8 - 8 + ( 7 - 4 )", // = -77
"3 - 9 + 6 + 6 + 4 - 2 - 3 - 3 - 6 + ( 2 + ( 6 - 2 + 4 + 4 - 3 * 6 ) )", // = -8
"8 + 5 + 3 + ( 3 - 1 * 8 + ( 3 * 9 * 7 - 4 * 7 * 1 + 5 - 1 + ( 5 - 8 ) ) )", // = 173
};
int answer[] = { 4, 8, -78, -182, -680, -6, 205, -77, -8, 173 };
for (int tc = 0; tc < 10; tc++)
{
int len;
char* testFormula = formula[tc];
for (len = 0; testFormula[len]; len++);
for (int i = 0; testFormula[i]; i++)
{
if ('0' <= testFormula[i] && testFormula[i] <= '9') testFormula[i] -= '0';
else if (testFormula[i] == '(') stack[sp++] = i;
else if (testFormula[i] == ')')
{
pair[i] = stack[sp - 1];
pair[stack[sp - 1]] = i;
sp--;
}
}
int ret = calculateInfix(testFormula, 0, len);
char ox = (ret == answer[tc]) ? 'o' : 'x';
printf("[tc :%02d]\ncal: %d\nanswer : %d (%c)\n\n", tc + 1, ret, answer[tc], ox);
}
return 0;
}'알고리즘 > [EXP] 삼성 SW 역량 테스트 C형' 카테고리의 다른 글
| 더블 링크드 리스트 구현 (Double Linked List) (0) | 2023.07.30 |
|---|---|
| BOJ 10757 : 큰 수 A+B with 10^N진법 (0) | 2023.07.29 |
| BOJ 15688 : 수 정렬하기 5 with In-Place Sort (0) | 2023.07.29 |
| 중위 표기식 직접 연산하기 (0) | 2023.07.29 |
| 포인터의 크기 (Size of Pointer) - 삼성 SW 역량 시험 환경 (0) | 2021.03.20 |
댓글