중위 표기식은 연산의 순서에 대한 정보가 없고 대신 연산의 우선순위가 정의되어 있다.
이를 소괄호를 파악하여 그 부분을 먼저 연산, 연산자의 우선순위를 근거로 연산의 순위를 결정하여 컴퓨터가 계산하기 쉬운 후위 표기식으로 변환하는 것이 계산기 프로그램 구현의 첫 걸음이다.
후위표기식 : 피연산자들이 앞, 연산자들이 뒤(후위)에 표기되어있는 식
중위 표기 -> 후위 표기 Rule (소괄호가 없을 때)
우선 피연산자는 새로운 문자열에, 연산자는 stack에 저장하는게 원칙이다.
이 때, 새로운 연산자를 문자열에서 만났을 때, stack의 top index와 비교하여 새로운 연산자의 우선순위가 더 높다면 새로운 연산자를 스택에 쌓고, 더 낮다면 스택에 쌓여있는 연산자를 피연산자가 저장되고 있는 문자열에 저장한다.
마지막까지 스택에 남아있는 연산자들은 하나씩 pop하여 문자열에 저장한다.
고민될 수 있는 상황
스택에 연산자가 여러개가 있을 때 : 새로운 연산자와 하나하나 비교
연산자의 우선순위가 같은 상황 : 먼저 온 연산자가 먼저 연산되어야 하므로 우선순위가 더 높은 것으로 취급
중위 표기 -> 후위 표기 Rule (소괄호가 있을 때)
일단 강의에서 괄호의 연산 우선순위가 가장 낮다는 등의 이야기를 하는데 그대로 하니 맞지 않게 나오는 경우가 있어서 스스로 방법을 좀 생각해보았고
이는 괄호를 하나 더 만날 때마다 스택을 하나 더 만들어 해결하는 것이었다.
괄호안에 있는 것을 먼저 연산해야 하기 때문이다.
내가 구현한 중위표기식을 후위표기식으로 바꾸는 코드
찾아보니 백준에 문제가 있어 숫자 대신 문자를 이용하는 것으로 코드를 하나 짜보았다.
https://www.acmicpc.net/status?user_id=honeyricecake&problem_id=1918&from_mine=1
#include <stdio.h>
#include <string.h>
int comparison(char x, char y)
{
if (x == '*' || x == '/')
{
if (y == '*' || y == '/') return 0;
else return 1;
}
else return 0;
}
int main()
{
char array[101];
char brray[101] = {0};
char stack[51][3] = {0};//stack[cur][2]는 현재 스택의 행에 저장된 연산자의 개수
int cur = 0;//현재 스택의 행
int count = 0;//brray의 몇번째 칸에 저장할 것인가
int length;//array의 길이
int i,j;
scanf("%s", array);
length = strlen(array);
for (i = 0; i < length; i++)
{
if (64 < array[i]) brray[count++] = array[i];
else if(42<=array[i]&&array[i]<=47)
{
if (stack[cur][2] == 0) stack[cur][stack[cur][2]++] = array[i];
else if (stack[cur][2] == 1)
{
if (comparison(array[i], stack[cur][0])) stack[cur][stack[cur][2]++] = array[i];
else
{
brray[count++] = stack[cur][0];
stack[cur][0] = array[i];
}
}
else
{
brray[count++] = stack[cur][1];
if (comparison(array[i], stack[cur][0]))
{
stack[cur][stack[cur][2] - 1] = array[i];
}
else
{
brray[count++] = stack[cur][0];
stack[cur][0] = array[i];
stack[cur][2] = 1;
}
}
}
else if(array[i] == '(')//괄호 열 때
{
cur++;
}
else
{
for (j = stack[cur][2] - 1; j >= 0; j--)
{
brray[count++] = stack[cur][j];
}
stack[cur][2] = 0;
cur--;
}
}
for (i = cur; i >= 0; i--)//마지막에 스택 비우기
{
for (j = stack[i][2] - 1; j >= 0; j--) brray[count++] = stack[i][j];
}
printf("%s", brray);
return 0;
}강의에서 구현한 코드
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "ListBaseStack.h"//앞에서 만들어 놓은 ListBaseStack.h와 소스파일 이용
int GetOpPrec(char op)//받아온 연산자의 연산우선순위를 부여하는 함수
{
switch(op)
{
case '*':
case '/':
return 5;
case '+':
case '-':
return 3;
case '(':
return 1;
}
return -1; // 등록되지 않은 연산자
}
int WhoPrecOp(char op1, char op2)
{
int op1Prec = GetOpPrec(op1);
int op2Prec = GetOpPrec(op2);//GetOpPrec은 WhoPrecOP의 Help함수
if(op1Prec > op2Prec)
return 1;
else if(op1Prec < op2Prec)
return -1;
else
return 0;
}//우선 순위가 더 높은 것을 판별하는 함수
void ConvToRPNExp(char exp[])//바꿔야 하는 문자열 exp
{
Stack stack;
int expLen = strlen(exp);
char * convExp = (char*)malloc(expLen+1);//바꿀 문자열 convEXP, 맨 마지막의 널문자를 위해 explen + 1칸 할당
int i, idx=0;
char tok, popOp;
memset(convExp, 0, sizeof(char)*expLen+1);//처음에 convExp의 모든 칸 0으로 초기화 -> 동적할당한 배열을 0으로 초기화하는데 써먹기 좋은 함수 memset, 기억해두자.
StackInit(&stack);//stack을 초기화
for(i=0; i<expLen; i++)
{
tok = exp[i];
if(isdigit(tok))//isdigit을 위해 ctype헤더파일을 추가
isdigit은 문자가 숫자이면 0이 아닌 숫자를 반환한다.
{
convExp[idx++] = tok;
}
else//문자가 숫자가 아닌 연산자라면
{
switch(tok)
{
case '(':
SPush(&stack, tok);//정의한 함수 SPush를 이용 stack에 (를 집어넣는다.
break;
case ')'://닫는 괄호이면
while(1)
{
popOp = SPop(&stack);//stack에서 저장된 연산자들을 꺼낸다.
if(popOp == '(')
break;//저장된 연산자가 개괄호이면 break, 개괄호는 스택에서 사라짐.
convExp[idx++] = popOp;//개괄호가 아니면 popOp를 convExp에 저장.
}
break;
case '+': case '-':
case '*': case '/'://이런 식으로 switch를 활용할 수 있구나.
while(!SIsEmpty(&stack) &&
WhoPrecOp(SPeek(&stack), tok) >= 0)
convExp[idx++] = SPop(&stack);
//tok의 연산자 우선순위보다 스택의 topindex의 연산자의 우선순위가 높거나 같으면(같아도 먼저 나왔으므로 우선순위가 더 높음)
연산자의 우선순위가 높은데 나중에 나올 수 없으므로 convExp에 연산자 저장
SPush(&stack, tok);//tok는 무조건 스택에 저장
break;
}
}
}