부울 표현식 구문 분석

1106. 부울 표현식 구문 분석

난이도:어려움

주제: 문자열, 스택, 재귀

부울 표현식은 참 또는 거짓으로 평가되는 표현식입니다. 다음 모양 중 하나일 수 있습니다.

• 't'는 true로 평가됩니다.
• false로 평가되는 'f'입니다.
• 내부 표현식 subExpr.의 논리적 NOT
으로 평가되는 '!(subExpr)'
• 내부의 _{논리적 AND}로 평가되는 '&(subExpr₁, subExpr₂, ..., subExprn)' 표현식 subExpr₁, subExpr₂, ..., subExpr_n 여기서 n >= 1.
• 내부의 _{논리 OR}로 평가되는 '|(subExpr₁, subExpr₂, ..., subExprn)' 표현식 subExpr₁, subExpr₂, ..., subExpr_n 여기서 n >= 1.

부울 표현식을 나타내는 문자열 표현식이 있는 경우 해당 표현식의 평가를 반환합니다.

주어진 표현이 유효하고 주어진 규칙을 따르는 것이 보장됩니다.

예 1:

• 입력: 표현식 = "&(|(f))"
• 출력: false
• 설명:
  • 먼저 |(f) --> 에프. 이제 표현은 "&(f)"입니다.
  • 그런 다음 &(f) --> 에프. 이제 표현은 "f"입니다.
  • 마지막으로 false를 반환합니다.

예 2:

• 입력: 표현식 = "|(f,f,f,t)"
• 출력: true
• 설명: (false OR false OR false OR true)의 평가는 true입니다.

예 3:

• 입력: 표현식 = "!(&(f,t))"
• 출력: true
• 설명:
  • 먼저 &(f,t) -->를 평가합니다. (거짓 AND 참) --> 거짓 --> 에프. 이제 표현식은 "!(f)"입니다.
  • 그런 다음 !(f) -->를 평가합니다. 거짓이 아님 --> 진실. true를 반환합니다.

제약조건:

• 1 <= 표현식.길이 <= 2 * 10⁴
• 표현식[i]은 '(', ')', '&', '|', '!', 't', 'f' 및 ',' 다음 문자 중 하나입니다.

힌트:

1. 도우미 함수 "parse_or", "parse_and", "parse_not"을 호출하는 "parse" 함수를 작성하세요.

해결책:

우리는 솔루션을 다양한 유형의 표현식 구문 분석 및 평가를 처리하는 더 작은 함수(parse_or,parse_and,parse_not)와 표현식의 구문 분석을 재귀적으로 처리하는 기본 구문 분석 함수로 분류할 것입니다. 스택을 사용하여 중첩된 표현식을 추적하고 단계별로 평가하겠습니다.

접근하다:

1. 파싱 및 재귀:

   • 중첩된 괄호를 발견할 때 스택을 사용하여 표현식을 추적하세요.
   • 문자를 순차적으로 처리하고 중첩 평가를 위해 스택을 관리합니다.
   • 닫는 괄호 )가 나타나면 마지막 표현식 세트를 추출하고 논리 연산(&, | 또는 !)을 적용하세요.

2. 도우미 기능:

   • parse_or: 하나 이상의 하위 표현식이 true인 경우 true를 반환하여 |(expr1, expr2, ..., exprN)을 평가합니다.
   • parse_and: 모든 하위 표현식이 true인 경우에만 true를 반환하여 &(expr1, expr2, ..., exprN)를 평가합니다.
   • parse_not: 하위 표현식의 반대를 반환하여 !(expr)을 평가합니다.

3. 표현식 처리:

   • t와 f와 같은 단일 문자는 참과 거짓으로 직접 변환됩니다.
   • 연산(&, |, !)이 발생하면 해당 규칙에 따라 내부 표현식이 평가됩니다.

PHP에서 이 솔루션을 구현해 보겠습니다. 1106. 불리언 표현식 파싱

  
  
  설명:




주요 함수(parseBooleanExpression):


식을 반복하고 문자를 스택에 푸시합니다.
 )가 발생하면 괄호 안의 모든 요소를 ​​수집하고 연산(&, |, !)을 기준으로 평가합니다.
결과를 't'(true) 또는 'f'(false)로 변환하고 다시 스택에 푸시합니다.







도우미 기능:



parse_and: 모든 하위 표현식이 't'(true)인 경우 true를 반환합니다.

parse_or: 하위 표현식이 't'인 경우 true를 반환합니다.

parse_not: 단일 하위 표현식의 부울 값을 반대로 바꿉니다.








  
  
  예제 연습:




입력: "&(|(f))"


스택 처리:



&, (, |, (, f, ), ) → 내부 표현식 |(f)는 f로 평가됩니다.
결과적으로 &(f)는 f로 평가됩니다.


출력: false.



입력: "|(f,f,f,t)"


평가 | 작업:


't'를 하나 찾으면 true로 평가됩니다.


출력: true.



입력: "!(&(f,t))"

스택 처리:



!, (, &, (, f, ,, t, ), ) → &(f,t)는 f로 평가됩니다.

!(f)는 true로 평가됩니다.


출력: true.





  
  
  복잡성:




시간 복잡도: O(N), 여기서 N은 표현식의 길이입니다. 각 문자는 제한된 횟수만큼 처리됩니다.

공간 복잡도: O(N), 중첩된 표현식을 추적하는 데 사용되는 스택으로 인해 발생합니다.


이 솔루션은 제약 조건에 매우 적합하며 입력 크기를 효과적으로 처리해야 합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 부울 표현식 구문 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!