삼항 표현식을 포함하는 표현식이 있다고 가정하고 표현식의 결과를 평가해야 합니다. True 및 False 및 "?"에 대한 T 및 F와 같은 일부 값을 지원합니다. 및 ":" 문자. 몇 가지 속성이 있습니다.
- 주어진 문자열의 길이는 10000보다 작거나 같아야 합니다.
- 조건식 그룹은 오른쪽에서 왼쪽입니다.
- 조건은 항상 T 또는 F입니다. 따라서 조건은 결코 숫자가 아닙니다.
- 표현식의 결과는 항상 T 또는 F로 평가됩니다.
예를 들어 입력이 "T ? 티 ? F :T :T”이므로 출력은 F가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 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 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
#include
using namespace std;
class Solution {
public:
string parseTernary(string s) {
string ret = "";
int n = s.size();
stack 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("T?T?F:T:T"));
} 입력
" T?T?F:T:T"
출력
F