(0 & (1 | 0) | 1) & (0 | 1)과 같은 문자열을 해당 진리 값으로 변환합니다.

Question

인터뷰 포럼에서이를 발견했으며 흥미로운 질문이라고 생각했습니다. C++에서이 작업을 수행하는 간단한 방법이 있습니까? 예를 들어 다음과 같은 함수 선언이 있다고 가정합니다.

bool _transform(string x); 
/* x is a combination of (,), 0, 1, &, and | such that all expressions 
    start with a open and ending brace, and the function evaluates the 
    strings actual truth value 
*/ 

이 작업을 수행하는 데 효율적이고 비교적 간단한 방법이 있습니까? 재귀 적으로 괄호를 닫는 방법을 생각했지만 문제는 어려워 보입니다.

Answer 1

산술 연산 대신 논리 연산을 사용하는 식 구문 분석 및 평가에서 오히려 간단한 작업입니다. 사소한 것. '재귀 적 하강 표현 구문 분석'또는 Dijkstra Shunting-yard 알고리즘을 찾으십시오. 경고 : 후자의 많은 자생 및 기타 유사 제품이 있으며, 대부분 미묘한 버그 또는 비선형 성능이 있습니다. 소스를 사용하십시오.

는 NB 제목의 식의 값이 1.

Answer 2

이 문제에 대한 간단한 해결책은 스택 기반 파서이다. [재귀 적 강하는 과도합니다.]

For each character in the string 
    If it's a value (0 1) 
    If top of stack is an operator 
     Pop operator and value, evaluate 
    Push value on the stack 
    If it's an operator (&|) push it on the stack 
    If it's a left parenthesis push it on the stack 
    If it's a right parenthesis pop the value and the LP, push the value 
At end, pop the value off the stack. 

정상적으로 오류를 처리하는 데 더 많은 코드가 필요하지만 아이디어를 얻을 수 있습니다. 또한 우선 순위를 무시합니다.

이 개념은 모든 종류의 산술 표현식으로 확장하기가 쉽지만 올바른 대답을 얻으려면 우선 순위를 처리해야합니다. 효과적으로 이것은 중위 표기법에서 후치 표기법으로 표현을 변형시키고 즉각 평가합니다.