[정올 1105] 수식 계산기2

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=385&sca=99&sfl=wr_hit&stx=1105 

JUNGOL

이 문제는 수식을 처음부터 차례로 읽으면서, 연산자와 피연산자를 구별하여 각각에 스택에 담으면서 계산해야 한다.

특히 연산자를 스택에 담을 때, 연산자의 우선순위가 "소괄호() > *와 / > +와 -" 이므로 이 우선순위 처리를 잘 해 주어야 한다.

#include <stdio.h>

enum {
	output = 0,
	cmd,
};

struct N {
	char c;
	long long val;
	N(char myc = 0, long long myval = 0) : c(0), val(0) {}
} st[2][205];
char arr[205];
int sp[2];

void push_back(N val, int stn) {	st[stn][sp[stn]++] = val; }
N pop(int stn) { 
	if (sp == 0) {		N rt(-1,0);		return rt;	}
	else return st[stn][--sp[stn]]; }

long long getnum(int& ri) {
	long long rt = 0;
	while (arr[ri] >= '0' && arr[ri] <= '9') {
		rt = (rt * 10) + arr[ri++] - '0';
	}
	return rt;
}

int getCmdPri(char cmd) {
	//숫자가 작은 게 우선순위가 높은 것
	if (cmd == '(') return 1;
	else if (cmd == '*' || cmd == '/') return 2;
	else if (cmd == '+' || cmd == '-') return 3;
	else return 4;
}

int cmpcmd(char ca, char cb) {
	//연산자 비교, ca 우선순위가 크면 1 리턴, 작으면 -1 리턴 같으면 0
	int cai = getCmdPri(ca);
	int cbi = getCmdPri(cb);
	if (cai < cbi) return 1;
	else if (cai == cbi) return 0;
	else return -1;
}

int main(void) {
	scanf("%s", arr); //후위 연산자로 만들어서 st[output]에 넣을 예정
	for (int i = 0; arr[i] != 0;) {
		N my, stcmd;
		if (arr[i] < '0' || arr[i] > '9') 
		{ //연산자인경우
			my.c = arr[i++];
			if (my.c == ')') { 
				//닫는 괄호라면, 여는 괄호 나올 때까지 전부 연산자 pop하여 출력
				while (sp[cmd]) 
				{
					stcmd = pop(cmd);
					if (stcmd.c == '(') break;
					else push_back(stcmd, output);
				}
			}
			else { 
				//닫는 괄호가 아니라면, 연산자 우선순위를 비교한다.
				if (sp[cmd]) 
				{ //연산자 스택이 비지 않았다면
					stcmd = pop(cmd); //현재 스택의 연산자와 비교해서
					if (stcmd.c == '(' || cmpcmd(my.c, stcmd.c) == 1) { 
						//새로운 연산자가 높으면 push back만 한다.
						push_back(stcmd, cmd);
					}
					else { 
						//새로운 연산자가 같거나 낮으면, 스택의 연산자를 출력하고 현재 연산자는 push back
						push_back(stcmd, output);
					}
				}
				
				if (my.c == '-' && arr[i] >= '0' && arr[i] <= '9') { 
					//만약 연산자가 -인데 바로 뒤에 숫자가 오는 경우, 마이너스 처리한다.
					my.c = '+';
					push_back(my, cmd); //새로운 연산자는 무조건 넣는다.
					my.c = 0;
					my.val = -getnum(i); //그 다음 숫자를 -처리해서 넣는다.
					push_back(my, output); //스택에 넣는다.
				}
				else	push_back(my, cmd); //새로운 연산자는 무조건 넣는다.
			}
		}
		else { 
			//피연산자인 경우
			my.val = getnum(i);
			push_back(my, output); //스택에 넣는다.
		}
	}
	while (sp[cmd])	{ //수식을 끝까지 읽었으면, 
		push_back(pop(cmd), output);
	}//후위 표기로 변환 완료
	//계산
	for (int i = 0; i < sp[output]; i++) {
		//앞에서 하나씩 읽어가면서
		N my = st[output][i];
		if (my.c == 0) { 
			//피연산자면
			push_back(my, cmd);
		}
		else { 
			//연산자면, 피연산자 2개 꺼내서 계산 후 다시 push_back
			N N1, N2;
			N2 = pop(cmd);
			N1 = pop(cmd);
			switch (my.c) {
			case '+':	N1.val += N2.val;	break;
			case '-':	N1.val -= N2.val;	break;
			case '*':	N1.val *= N2.val;	break;
			case '/':	N1.val /= N2.val;	break;
			default: break;
			}
			push_back(N1, cmd);
		}
	}
	printf("%lld\n", st[cmd][0].val);

	return 0;
}