การประเมินแผนผังนิพจน์ในภาษา 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