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

오리지널 소스  : c++로 쉽게 풀어쓴 자료구조

밑은 좀더 코드를 쉽게 이해하기 쉽게 정리해본 코드

후위 계산은 괄호가 필요없다(연산의 우선순위를 생각안해도 된다)는 큰 장점이 있다. 순서대로 컴퓨터가 처리하기 편하다.

a b c + *

가 있을 때, 연산자를 읽을 때마다 스택에서 두 개의 수를 꺼내서 계산하고 그 결과값을 스택에 넣어둔다.

단계 (0) : push a

단계 (1) : push b

단계 (2) : push c

단계 (3) :

pop = c

pop = b

push b + c

단계 (4) : push a * (b + c)

단계 (5) : 더이상 읽을 문자가 없으므로 top에 담긴 a * (b + c) 값 반환

double calcPostfixExpr(FILE* fp = stdin)

{

char c{};

ArrayStack<double, 32> numSt;

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

{

if (c >= '0' && c <= '9')

{

cin.putback(c);

double val{};

cin >> val;

numSt.push(val);

}

else if (isOp(c, "+-*/"))

{

double latter = numSt.peekAndPop();

double former = numSt.peekAndPop();

numSt.push(calBinaryOp(c, latter, former));

}

}

return numSt.top();

}

c >= '0' && c <= '9'

은 isdigit으로 바꿀까 했는데 이미 충분히 분명하기에 그냥 놔두기로 했다.

bool isOp(char c, char* ops)

{

for (size_t i = 0; ops[i]; ++i)

{

if (c == ops[i]) return true;

}

return false;

}

double calBinaryOp(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 ("divided by zero\n");

return former / latter;

}

}

인자의 순서가 former, latter가 아닌 latter, former인 이유는 

실행순서상 변수에 한번 담지 않고 바로 입력할 수도 있게 하기 위함이다.

numSt.push(calBinaryOp(c, numSt.peekAndPop(), numSt.peekAndPop()));

이런식으로, 하지만 가독성이 별로인 것 같아서 그냥 놔둠

int main()

try{

cout << calcPostfixExpr();

return 0;

}

catch(exception& e)

{

cout << e.what() << endl;

}

사용한 스택은 http://kid5.tistory.com/256?category=740150