백준 1918번 후위표기식

문제링크 : https://www.acmicpc.net/problem/1918

 

 

 

알고리즘

1. 문자면 출력값에 더해주고 여는 괄호면 스택에 push , 닫히는 괄호면 스택이 비거나 top이 여는 괄호 일 때까지 pop     하면서 출력값에 더해줌.

2.사칙연산을 처리 해준다.

 

 

코드

 

#include<iostream>
#include <stack>
 
using namespace std;
 
int main() {
   string str;
   cin >> str;
 
   string result;
   stack<char> s;
 
 
   for (int i = 0; i < str.length(); i++) {
      //문자면 출력값에 더함.
      if ('A' <= str[i] && str[i] <= 'Z') {
         result += str[i];
      }
 
      else {
         //여는 괄호 면 스택에 push
         if (str[i] == '(') {
            s.push(str[i]);
         }
         //닫히는 가로면 스택이 비거나 top 이 '(' 일떄까지
         //pop 하면서 결과값에 더해줌.
         else if (str[i] == ')') {
            while (!s.empty() && s.top() != '(') {
               result += s.top();
               s.pop();
            }
            //마지막에 여는괄호 pop
            if (!s.empty())
               s.pop();
         }
         //사칙연산
         else if (str[i] == '*' || str[i] == '/') {
            while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
               result += s.top();
               s.pop();
            }
            s.push(str[i]);
         }
         else if (str[i] == '+' || str[i] == '-') {
            while (!s.empty() && s.top() != '(')
            {
               result += s.top();
               s.pop();
            }
            s.push(str[i]);
         }
      }
   }
 
   while (!s.empty()) {
      result += s.top();
      s.pop();
   }
 
   cout << result << "\n";
}