구현 - 스택 응용 문제 - 중위계산

책에는 중위계산을 후위계산으로 바꾸는 법이 나와있는데

연습할겸 중위계산을 바로 결과로 보여주기로 했다.

코드가 점점 복잡해져서 작동한 뒤에는 좀더 서술적인 함수이름으로 정리해보았다.

느낀점은 일단 예전에 PPP C++에서 작성해본 구문분석형 계산기보다 기능추가가 훨씬 힘들고, 코드 읽는 것도 힘들다.

중위계산을 후위계산으로 바꿀 때 

중위계산은 연산자를 저장해두었다가 나중에 봐야하므로 숫자와 연산자를 위한 스택을 따로 준비했다.

1+2*4+1 를 진행해보자.

단계(0) : 1을 숫자스택에 담는다.

단계(1) : +을 연산스택에 담는다.

단계(2) : 2를 숫자스택에 담는다.

단계(3) : *를 읽었다. *를 연산스택의 top인 +와 비교한다. *의 순위는 +보다 높으므로 별일없이 스택에 담아둔다.

단계(4) : 4를 숫자스택에 담는다.

단계(5) : +를 읽었다. 단계(3)과 마찬가지로, top인 *과 비교한다. 이번엔 반대로 *가 높으므로 *의 연산을 먼저 진행한다.

가장 위에서부터 4와 2를 스택에서 빼고 2*4 = 8을 숫자 스택에 담는다. 연산스택의 pop으로 *를 제거한다.

단계(5)의 과정은 더이상 현재 연산자인 +보다 높거나 같은 연산자가 없을 때까지 계속 진행된다.

여기에서 다음 연산자는 처음에 담은 +다. +와 +는 같으므로 스택에 담긴 8과 1의 + 연산을 진행한다. 기존의 +는 pop.

이제 숫자 스택에는 9만, 연산 스택에는 새 +만 남았다.

단계(6) : 1을 숫자스택에 담는다.

단계(7) : 더이상 읽을 문자가 없다. 숫자 스택에 남은 1과 9, 연산 스택의 +로 마지막 계산을 한다. (이 과정은 더이상 연산자가 없을 때까지 반복된다.)

결과는 9 + 1인 10이 되었다.

괄호 처리

(는 우선순위가 제일 낮아 다음 연산자에 영향을 주지 않는다.

)는 (가 나올 때 까지 괄호안의 남은 연산을 진행한다. 괄호 외의 연산을 무시하는 효과가 있다.

2 * (3 + 4) - 4   는  2 3 4 + * 4 - 이 될 것이다.

이를 코드로 표현했더니 다음과 같다.

constexpr int arrSize = 32;

double calcul_infix_expression(FILE* fp = stdin)

{

char cCur{};

ArrayStack<double, arrSize > numStack;

ArrayStack<char, arrSize > opStack;

while ((cCur = getc(fp)) != '\n')

{

switch (cCur)

{

case '0': case '1':case '2':case '3':case '4':

case '5': case '6':case '7':case '8':case '9':

numStack.push(get_complte_number(cCur));

break;

case '+': case '-': case '*': case '/':

deal_operators(cCur, numStack, opStack);

break;

case '(': case ')':

deal_parentheses(cCur, numStack, opStack);

break;

}

}

calcul_stack_remains(cCur, numStack, opStack);

return numStack.top();

}

double get_complte_number(char cCur)

{

cin.putback(cCur);

double val{};

cin >> val;

return val;

}

void deal_operators(char token, ArrayStack<double, arrSize >& numStack, ArrayStack<char, arrSize >& opStack)

{

while (!opStack.isEmpty())

{

char topOp = opStack.top();

if (opPriority(topOp) >= opPriority(token))

{

push_calculated_result(topOp, numStack);

opStack.pop();

}

else break;

}

opStack.push(token);

}

int opPriority(char n)

{

switch (n)

{

case '(': case ')': return 0;

case '+': case '-': return 1;

case '*': case '/': return 2;

}

return -1;

}

void push_calculated_result(char topOp, ArrayStack<double, arrSize >& numStack)

{

double latter = numStack.peekAndPop();

double former = numStack.peekAndPop();

numStack.push(calcul_binary_Op(topOp, latter, former));

}

double calcul_binary_Op(char op, double latter, double former)

{

switch (op)

{

case '+': return former + latter;

case '-': return former - latter;

case '*': return former * latter;

case '/':

if (latter == 0) throw exception("divided by zero : calcul_binary_Op\n");

return former / latter;

}

throw exception(" No Return : calcul_binary_Op\n");

}

void deal_parentheses(char token, ArrayStack<double, arrSize >& numStack, ArrayStack<char, arrSize >& opStack)

{

if (token == '(')

{

opStack.push(token);

return;

}

else if (token == ')')

{

while (!opStack.isEmpty())

{

char topOp;

topOp = opStack.peekAndPop();

if (topOp == '(') break;

else

push_calculated_result(topOp, numStack);

}

}

}

void calcul_stack_remains(char token, ArrayStack<double, arrSize >& numStack, ArrayStack<char, arrSize >& opStack)

{

while (!opStack.isEmpty())

{

char topOp = opStack.top();

push_calculated_result(topOp, numStack);

opStack.pop();

}

}

int main()

{

while (true)

try{

cout << calcul_infix_expression() << endl;

}

catch (exception& e){

cout << e.what();

}

return 0;

}