Java의 산술 표현식에서 트리를 구문 분석하고 구축하는 방법은 무엇입니까?

Java에서 산술식 구문 분석 및 트리 작성

소개

산술식 구문 분석 및 등가 트리 구성 컴파일러 설계와 언어처리에 있어 필수적인 작업입니다. 이 기사에서는 Java에서 산술 표현식을 구문 분석하고 트리 표현을 생성하는 방법을 보여줍니다.

표현식 구문 분석

표현식을 구문 분석하려면 스택을 사용할 수 있습니다. 기반 알고리즘. 표현식을 반복하면서 다음과 같이 합니다.

• 여는 괄호를 스택에 푸시합니다.
• 숫자와 연산자를 스택에 푸시합니다.
• 닫는 괄호가 나타나면 다음을 평가합니다. 일치하는 여는 괄호에 도달할 때까지 스택을 팝하여 하위 트리를 만든 다음 결과를 스택에 푸시합니다.

트리 구축

식이 구문 분석되면, 스택에서 트리 노드를 만들 수 있습니다.

• 리프 노드: 정수는 LeafInt 노드가 됩니다.
• 연산자 노드: 연산자는 다음과 같습니다. PlusOp, MinusOp, MultOp 또는 DivOp 클래스가 있는 노드와 그 자식은 스택에서 팝됩니다.

예

(5 2) 표현식을 고려하세요. *7:

<code class="java">Stack<Node> stack = new Stack<>();
stack.push(new LeafInt(5));
stack.push(new PlusOp());
stack.push(new LeafInt(2));
stack.push(new MultOp());
stack.push(new LeafInt(7));
while (stack.size() > 1) {
  Node right = stack.pop();
  Operator op = (Operator) stack.pop();
  Node left = stack.pop();
  stack.push(new OpNode(op, left, right));
}</code>

결과 트리의 구조는 다음과 같습니다.

    *
   / \
  +   7
 / \
5   2

음수 및 괄호 처리

음수 처리 숫자는 5-2 대신 5(-2)로 표현하세요. 음수 기호는 항상 단항 우선순위를 가집니다. 마찬가지로 괄호는 연산 순서를 강제합니다.

검증

정확성을 보장하려면 다음을 확인하여 표현식을 검증하십시오.

• 여는 괄호에는 닫는 괄호가 일치합니다.
• 각 연산자에는 올바른 수의 피연산자가 있습니다.

결론

스택 기반 알고리즘을 사용하면 산술 표현식을 구문 분석하고 동등한 트리 표현을 구축하는 것이 간단합니다. 이 접근 방식은 Java의 산술 표현식을 추가로 분석하고 조작하기 위한 신뢰할 수 있는 기반을 제공합니다.

위 내용은 Java의 산술 표현식에서 트리를 구문 분석하고 구축하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!