[1918] 후위표기식

https://www.acmicpc.net/problem/1918

어떤 회사의 인턴 사전 시험에서 스택 계산기 문제가 나왔습니다.

식을 문자열로 받고 계산하는 문제였는데..

총 7문제?? 정도였던것 같은데.. 손코딩으로 해야해서..

시간이 모잘라서 못풀었습니다ㅠ_ㅠ

기억도 되살릴겸 다시 풀어봤습니다!

----------------------------------------

어떤식을 후위연산으로 바꿀 때 중요한 것은

기호들의 우선순위 입니다.

*, / 곱하기와 나누기는 우선순위가 같습니다.

+, - 플러스와 마이너스는 우선순위가 같습니다.

위 두개의 우선순위는 ('+', '-') < ('*', '/') 이렇게 됩니다.

곱하기와 나누기가 플러스 마이너스 보다 우선순위가 높은 것이지요.

예를 들어 설명해드리자면!

3 + 4 * 8 이라는 식이 있으면 답은 3 + 32 = 35 겠지요!?

여기서 * 곱하기를 먼저 계산하셨을겁니다! 이 우선순위를 말하는 것입니다!

ABC+*라는 식은 A * (B + C)입니다.

A * (B + C)라는 식을 후위연산으로 바꾸는 과정을 보여드릴게요!

스택은 왼쪽이 bottom 가장 오른쪽이 탑입니다.

출력은 그냥 왼쪽부터 오른쪽 순입니다.

먼저 A를 만났습니다.

1.

스택 :

출력 : A

가 되겠죠?

과정을 쭉 보여드릴게요오오~~

2.

스택 : *

출력 : A

3.

스택 : *(

출력 : A

4.

스택 : *(

출력 : AB

5.

스택 : *(+

출력 : AB

6.

스택 : *(+

출력 : ABC

7.

이제 여기서 중요합니다!

')' 기호를 만나면 ! 스택에서 '(' 까지 전부 pop 해줍니다!!!! 여기서는 + 밖에없으므로!

스택 : *(+

출력 : ABC

스택 : *

출력 : ABC+

가 됩니다!

이제 문자열이 끝났으니

스택에 남아있는것을 스택이 empty가 될때까지 비워주면서 차례차례 출력 문자열에 넣어줍니다!

결과 : ABC+*

가 됩니다!

ABC*+라는식은 A + B * C입니다.

A + B * C 를 한번 위의 절차처럼 따라해보세요!!!

주의할 점은 *가 +보다 우선순위가 높다는 점!

아래는 1918 문제의 코드입니다.

#include <cstdio>
#include <iostream>
#include <utility>
#include <stack>
#include <string.h>
using namespace std;
 
int main() {
    char str[1000]; //input
    char output[1000]; // output
 
    scanf("%s", str);
 
    stack<char> s; // +-*/(를 저장할 스택
    int oIdx = 0; // 출력 문자열의 인덱스
 
    // str의 문자열을 끝까지
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] >= 'A' && str[i] <= 'Z') output[oIdx++] = str[i]; // A~Z는 출력문자열에 추가
        else {
            //그게아니면 전부 기호이므로
            //아래처럼 처리
 
            if (str[i] == '(') s.push(str[i]); // '('문자는 무조건 스택에 추가
            else if (str[i] == ')') { // ')'문자는 '('문자를 만날 때까지 pop
                while (s.top() != '(') {
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.pop();
            }
            else if (str[i] == '*' || str[i] == '/') {
                //우선순위가 나보다 높거나 같은것을 pop
                //( '/','*'보다 우선순위가 높은것은 없음)
                while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.push(str[i]);
            }
            else { // '+', '-' 인 경우
                while (!s.empty() && s.top() != '(') {
                    //우선순위가 나보다 높거나 같은것을 pop
                    //('+', '-'보다는 전부 우선순위가 높으므로 '('나 스택이 빌 때까지 pop)
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.push(str[i]);
 
            }
        }
    }
 
    //스택에 남아있는 것을 전부 pop
    while (!s.empty()) {
        output[oIdx++] = s.top();
        s.pop();
    }
    output[oIdx] = '\0';
 
    printf("%s\n", output);
 
    return 0;
}