Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 우선순위큐
  • 위상 정렬
  • 문자열
  • 백준
  • 정수론
  • 투포인터
  • 수학
  • 백트래킹
  • 구현
  • 브루트포스
  • KMP
  • 기하
  • LCA
  • 세그먼트 트리
  • 유니온 파인드
  • 트라이
  • 이분탐색
  • 최소 스패닝 트리
  • 누적합
  • UC++
  • 그래프
  • 조합론
  • 트리
  • 정렬
  • 분할정복
  • 스택
  • C++
  • 동적계획법
  • SCC
  • 큐

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 1918번 문제
공부 및 정리/백준 코드

[C++]백준 - 1918번 문제

2022. 10. 25. 11:08

1918번: 후위 표기식 (acmicpc.net)

 

1918번: 후위 표기식

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의

www.acmicpc.net

 

1918번 : 후위 표기식


수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

결과: ABC*+DE/-

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

 

입력


첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. 

 

 

출력


첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

 

 

 


 

생각해 볼 점


중위표기 -> 후위표기 문제입니다.

 

알고리즘은 이렇습니다.

 

1. 문자는 그냥 출력한다.

2. 사칙 연산은 '+', '-' 는 1, '*', '/'는 2의 우선순위를 갖는다.

3. 괄호는 0의 우선순위를 갖지만, 따로 처리한다.

4. 사칙연산은 스택이 비어있거나 우선순위가 더 높은 경우 push한다.

5. 스택의 top이 현재 처리할 사칙연산보다 낮거나 같은 우선순위를 가진 경우 모두 출력하고 push한다.

6. '('는 그냥 push하고 ')'는 '('를 만날때까지 출력한다.

 

아래 예제 처리를 보면서 자세히 알아봅시다.

 

1. 초기상태
2. 문자는 그냥 출력
3. 연산자 push
4. 문자는 그냥 출력
5. 우선순위가 더 높은 *는 push
6. 문자는 그냥 출력
7. 연산자 우선순위가 낮거나 같은 모든 스택 연산자 출력
8. 스택이 비었으므로 push
9. '('는 그냥 push
10. 문자는 그냥 출력
11. 연산자 우선순위가 '('보다 높으므로 push
12. 문자는 그냥 출력
13. '('를 만날때까지 pop
15. 수식이 종료됨
16. 스택 비우기

 

 

코드


#include <iostream>
#include <map>
#include <stack>

using namespace std;


int main()
{
    char input[101];
    scanf("%s", input);

    stack<char> st;
    map<char, int> order;

    //연산자 우선 순위 셋팅
    order['+'] = 1;
    order['-'] = 1;
    order['*'] = 2;
    order['/'] = 2;


    for(int i = 0; input[i]; i++)
    {
        char c = input[i];
        //숫자는 그냥 표기
        if('A' <= c && c <= 'Z')
        {
            printf("%c", c);
            continue;
        }

        //괄호 처리
        if(c == '(')
        {
            st.push('(');
            continue;
        }

        //괄호를 만날때까지 pop
        if(c == ')')
        {
            while(st.top() != '(')
            {
                printf("%c", st.top());
                st.pop();
            }
            st.pop();
            continue;
        }

        //우선 순위가 높은 연산자 모두 pop    
        while(!st.empty() && order[c] <= order[st.top()])
        {
            printf("%c", st.top());
            st.pop();
        }

        st.push(c);
    }

    //스택 비우기
    while(!st.empty())
    {
        printf("%c", st.top());
        st.pop();
    }
    return 0;
}

 

그 외


 

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++] 백준 - 1799번 문제  (0) 2022.10.27
[C++] 백준 - 1238번 문제  (0) 2022.10.26
[C++]백준 - 1865번 문제  (0) 2022.10.21
[C++]백준 - 16135번 문제  (0) 2022.10.14
[C++]백준 - 11659번 문제  (0) 2022.10.13
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++] 백준 - 1799번 문제
    • [C++] 백준 - 1238번 문제
    • [C++]백준 - 1865번 문제
    • [C++]백준 - 16135번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바