C++での式ツリーの評価

この問題では、+、-、/、*などの二項演算で構成される式ツリーが与えられます。式ツリーの評価を行ってから、結果を返す必要があります。

表現ツリー は特殊なタイプの二分木であり、各ノードは次のように分散される演算子またはオペランドで構成されます-

• ツリーのリーフノードは、操作が実行される値です。
• 非リーフノードは二項演算子で構成されます 実行する操作を示します。

問題を理解するために例を見てみましょう

入力：

出力： 1

説明：

式ツリーのデコード

Exp =（（5 + 9）/（2 * 7））
=（14/14）

= 1

ソリューションアプローチ：

この問題の簡単な解決策は、ルートからそれぞれ1つの操作を実行することです。オペランドについては、サブツリーを解決します。すべての操作はバイナリであるため、ツリーのノードには2つの子があるか、子がないかのどちらかです。

再帰を使用して、各ノードの二項演算を解決します。

ソリューションの動作を説明するプログラム

例

#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