C++의 삼항 표현식 파서

임의로 중첩된 삼항 표현식을 나타내는 문자열이 있다고 가정하고 표현식의 결과를 계산해야 합니다. 주어진 표현식이 유효하고 숫자 0-9, ?, :, T 및 F로만 구성되어 있다고 항상 가정할 수 있습니다. (여기서 T와 F는 각각 True와 False를 나타냅니다). 몇 가지 속성이 있습니다 -

주어진 문자열의 길이는 10000보다 작거나 같아야 합니다.
각 숫자에는 한 자리만 포함됩니다.
조건식 그룹은 오른쪽에서 왼쪽입니다.
조건은 항상 T 또는 F입니다. 따라서 조건은 결코 숫자가 아닙니다.
표현식의 결과는 항상 숫자 0-9, T 또는 F로 평가됩니다.

예를 들어 입력이 "F?1:T?4:5"와 같으면 출력은 4가 됩니다. 가장 오른쪽 표현식 "T?4:5"를 구문 분석하므로 4가 반환되고 기본 표현식은 "F?1:4"이므로 반환된 값은 4입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ret :=빈 문자열, n :=s 크기, 스택 생성 st
범위 n – 1에서 0까지의 I에 대해
- x :=s[i]
- st가 비어 있지 않고 스택의 맨 위가 '?'이면
  - st에서 삭제
  - first :=st의 맨 위, 스택에서 두 요소 삭제
  - 두 번째 :=스택의 맨 위, st에서 삭제
  - x가 T이면 첫 번째를 st에 삽입하고, 그렇지 않으면 두 번째를 st에 삽입
- 그렇지 않으면 x를 st
  에 삽입하십시오.
st가 비어 있지 않은 동안
- ret :=ret + st의 맨 위 및 st에서 삭제
리버스 ret 및 리턴 ret

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string parseTernary(string s) {
      string ret = "";
      int n = s.size();
      stack <char> st;
      for(int i = n - 1; i >= 0; i--){
         char x = s[i];
         if(!st.empty() && st.top() == '?'){
            st.pop();
            char first = st.top();
            st.pop();
            st.pop();
            char second = st.top();
            st.pop();
            if(x == 'T'){
               st.push(first);
            }
            else st.push(second);
            }
            else{
               st.push(x);
            }
         }
         while(!st.empty()){
            ret += st.top();
            st.pop();
         }
         reverse(ret.begin(), ret.end());
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.parseTernary("F?1:T?4:5"));
}

입력

"F?1:T?4:5"