스택을 활용해서 계산기를 만드는 연습문제이다.
중위표기식 -> 후위표기식 -> 후위표기식 계산 순서로 이루어진다.
먼저 중위표기식을 후위표기식으로 고쳐보자
1. 중위 to 후위
헤더
#ifndef __PostFix_h
#define __PostFix_h
void ConvertRPN(char exp[]);
#endif
소스
#include "Postfix.h"
#include <stdlib.h>
#include "CStack.h"
#include <string.h>
#include <ctype.h>
int PrecOP(char op1, char op2){
int op1_n = GetOp(op1);
int op2_n = GetOp(op2);
if(op1_n == -1 || op2_n == -1){
printf("에러");
exit(-1);
}
if(op1_n > op2_n) return 1;
else if(op1 < op2_n) return -1;
else return 0;
}
int GetOp(char op){
switch (op)
{
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
case '(':
return 0;
}
return -1;
}
void ConvertRPN(char exp[]){
Stack stack;
StackInit(&stack);
int lens = len(exp);
char temp[] = (char*)malloc(lens+1);
memset(temp,0,sizeof(char)*lens+1); //미리 0으로 초기화 해둠
int Tempindex =0;
for(int i=0; i<lens; i++){
char curChar = exp[i];
if(isdigit(curChar)){
temp[Tempindex++] = curChar;
}
else if(curChar == '(')
{
push(&stack,curChar);
}
else if(curChar == ')')
{
while(!itEmpty(&stack)){
char c = pop(&stack);
if(c == '(') break;
temp[Tempindex++] = c;
}
}
else{
while(!itEmpty(&stack) && PrecOP(peek(&stack),curChar)!= -1){
temp[Tempindex++] = pop(&stack);
}
pust(&stack,curChar);
}
}
while(!itEmpty(&stack)){
temp[Tempindex++] = pop(&stack);
}
strcpy(exp,temp);
free(temp);
}
> 중위표기식을 후위표기식으로 고치는 방법은 차량기지 알고리즘을 참고해보자.
- 피연산자가 나오면, 출력한다.
- 여는 괄호가 나오면, 스택에 추가한다.
- 닫는괄호가 나오면, 여는괄호가 나올 때 까지 스택에 모든 연산자를 출력한다 (단, 여는괄호는 출력x)
- 연산자는 스택 있는 연산자와 들어오려는 연산자의 우선순위를 비교한다.
> 스택에 있는 연산자가 들어오려는 연산자보다 우선순위가 높거나 같으면, 스택에 연산자 출력
> 스택에 연산자가 없거나, 우선순위가 낮은 연산자가 나올 때 까지 이를 반복한다.
다음은 후위표기식을 계산하는 함수를 정의한 헤더와 소스 파일이다.
2. 후위표기식 계산
헤더
#ifndef __Post_ca_H
#define __Post_ca_H
int SolRPN(char exp[]);
#endif
소스
#include <string.h>
#include <ctype.h>
#include "CStack.h"
#include "PostCal.h"
int SolRPN(char exp[]){
Stack stack;
StackInit(&stack);
for(int i=0; i<len(exp);i++){
if(isdigit(exp[i]))push(&stack,exp[i]);
else{
int backNumber = pop(&stack) -'0';
int frontNumber = pop(&stack) -'0';
switch (exp[i])
{
case '*':
push(&stack,frontNumber*backNumber);
break;
case '/':
push(&stack,frontNumber/backNumber);
break;
case '+':
push(&stack,frontNumber+backNumber);
break;
case '-':
push(&stack,frontNumber-backNumber);
break;
}
}
}
return pop(&stack);
}
스택을 이용해 간단하게 후위표기식을 계산할 수 있다.
주어진 후위표기식을 돌면서
> 피연산자는 스택에 넣는다.
> 연산자를 만나면, 스택에서 피연산자를 꺼내서 계산한 뒤에 다시 스택에 넣는다.
참고자료: 윤성우 열혈자료구조
차량기지 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 차량기지 알고리즘은 중위 표기법으로 표현된 수식을 분석할 때 사용할 수 있는 알고리즘이다. 알고리즘의 결과물은 역폴란드 표기법이나 파스 트리가 될 수
ko.wikipedia.org
관련 문제
https://www.acmicpc.net/problem/1918
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net