C++에서 표현식 트리 평가

이 문제에서는 +, - , /, *와 같은 이진 연산으로 구성된 표현식 트리가 제공됩니다. 표현식 트리를 평가한 다음 결과를 반환해야 합니다.

표현식 트리 각 노드가 다음과 같이 배포되는 연산자 또는 피연산자로 구성되는 특수한 유형의 이진 트리입니다.

• 트리의 리프 노드는 작업을 수행할 값입니다.
• 리프가 아닌 노드는 이항 연산자로 구성됨 수행할 작업을 나타냅니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력:

<강한>

출력: 1

설명:

표현식 트리 디코딩,

경험치 =( (5+9) / (2*7) )
=( 14 / 14 )

=1

해결 방법:

문제에 대한 간단한 해결책은 루트에서 각각 하나의 연산을 수행하는 것입니다. 피연산자의 경우 하위 트리를 해결할 것입니다. 모든 작업은 이진법이므로 트리의 노드에는 두 개의 자식이 있거나 전혀 없습니다.

재귀를 사용하여 각 노드의 이진 연산을 해결합니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#include <bits/stdc++.h>
using namespace std;

class node {
   
   public:
      string value;
      node *left = NULL, *right = NULL;
      node(string x)
      {
         value = x;
      }
};

int solveExpressionTree(node* root) {
   
   if (!root)
      return 0;

   if (!root->left &amp;&amp; !root->right)
      return stoi(root->value);

   int leftSubTreeSol = solveExpressionTree(root->left);
   int rightSubTreeSol = solveExpressionTree(root->right);

   if (root->value == "+")
      return leftSubTreeSol + rightSubTreeSol;

   if (root->value == "-")
      return leftSubTreeSol - rightSubTreeSol;

   if (root->value == "*")
      return leftSubTreeSol * rightSubTreeSol;
   
   if (root -> value == "/")
      return leftSubTreeSol / rightSubTreeSol;
   
   return -1;
}

int main()
{
   node *root = new node("/");
   root->left = new node("+");
   root->left->left = new node("9");
   root->left->right = new node("5");
   root->right = new node("*");
   root->right->left = new node("2");
   root->right->right = new node("7");
   cout<<"The evaluation of expression tree is "<<solveExpressionTree(root);
   return 0;
}

출력 -

The evaluation of expression tree is 1