Dado un árbol de expresión simple , que consta de operadores binarios básicos, es decir, +, –,* y / y algunos números enteros, evalúe el árbol de expresión.
Ejemplos:
C++
// C++ program to evaluate an expression tree
#include <bits/stdc++.h>
using namespace std;
// Class to represent the nodes of syntax tree
class node
{
public:
string info;
node *left = NULL, *right = NULL;
node(string x)
{
info = x;
}
};
// Utility function to return the integer value
// of a given string
int toInt(string s)
{
int num = 0;
// Check if the integral value is
// negative or not
// If it is not negative, generate the number
// normally
if(s[0]!='-')
for (int i=0; i<s.length(); i++)
num = num*10 + (int(s[i])-48);
// If it is negative, calculate the +ve number
// first ignoring the sign and invert the
// sign at the end
else
{
for (int i=1; i<s.length(); i++)
num = num*10 + (int(s[i])-48);
num = num*-1;
}
return num;
}
// This function receives a node of the syntax tree
// and recursively evaluates it
int eval(node* root)
{
// empty tree
if (!root)
return 0;
// leaf node i.e, an integer
if (!root->left && !root->right)
return toInt(root->info);
// Evaluate left subtree
int l_val = eval(root->left);
// Evaluate right subtree
int r_val = eval(root->right);
// Check which operator to apply
if (root->info=="+")
return l_val+r_val;
if (root->info=="-")
return l_val-r_val;
if (root->info=="*")
return l_val*r_val;
return l_val/r_val;
}
//driver function to check the above program
int main()
{
// create a syntax tree
node *root = new node("+");
root->left = new node("*");
root->left->left = new node("5");
root->left->right = new node("-4");
root->right = new node("-");
root->right->left = new node("100");
root->right->right = new node("20");
cout << eval(root) << endl;
delete(root);
root = new node("+");
root->left = new node("*");
root->left->left = new node("5");
root->left->right = new node("4");
root->right = new node("-");
root->right->left = new node("100");
root->right->right = new node("/");
root->right->right->left = new node("20");
root->right->right->right = new node("2");
cout << eval(root);
return 0;
}
Java
// Java program to evaluate expression tree
import java.lang.*;
class GFG{
Node root;
// Class to represent the nodes of syntax tree
public static class Node
{
String data;
Node left, right;
Node(String d)
{
data = d;
left = null;
right = null;
}
}
private static int toInt(String s)
{
int num = 0;
// Check if the integral value is
// negative or not
// If it is not negative, generate
// the number normally
if (s.charAt(0) != '-')
for(int i = 0; i < s.length(); i++)
num = num * 10 + ((int)s.charAt(i) - 48);
// If it is negative, calculate the +ve number
// first ignoring the sign and invert the
// sign at the end
else
{
for(int i = 1; i < s.length(); i++)
num = num * 10 + ((int)(s.charAt(i)) - 48);
num = num * -1;
}
return num;
}
// This function receives a node of the syntax
// tree and recursively evaluate it
public static int evalTree(Node root)
{
// Empty tree
if (root == null)
return 0;
// Leaf node i.e, an integer
if (root.left == null && root.right == null)
return toInt(root.data);
// Evaluate left subtree
int leftEval = evalTree(root.left);
// Evaluate right subtree
int rightEval = evalTree(root.right);
// Check which operator to apply
if (root.data.equals("+"))
return leftEval + rightEval;
if (root.data.equals("-"))
return leftEval - rightEval;
if (root.data.equals("*"))
return leftEval * rightEval;
return leftEval / rightEval;
}
// Driver code
public static void main(String[] args)
{
// Creating a sample tree
Node root = new Node("+");
root.left = new Node("*");
root.left.left = new Node("5");
root.left.right = new Node("-4");
root.right = new Node("-");
root.right.left = new Node("100");
root.right.right = new Node("20");
System.out.println(evalTree(root));
root = null;
// Creating a sample tree
root = new Node("+");
root.left = new Node("*");
root.left.left = new Node("5");
root.left.right = new Node("4");
root.right = new Node("-");
root.right.left = new Node("100");
root.right.right = new Node("/");
root.right.right.left = new Node("20");
root.right.right.right = new Node("2");
System.out.println(evalTree(root));
}
}
// This code is contributed by Ankit Gupta
Python3
# Python program to evaluate expression tree
# Class to represent the nodes of syntax tree
class node:
def __init__(self, value):
self.left = None
self.data = value
self.right = None
# This function receives a node of the syntax tree
# and recursively evaluate it
def evaluateExpressionTree(root):
# empty tree
if root is None:
return 0
# leaf node
if root.left is None and root.right is None:
return int(root.data)
# evaluate left tree
left_sum = evaluateExpressionTree(root.left)
# evaluate right tree
right_sum = evaluateExpressionTree(root.right)
# check which operation to apply
if root.data == '+':
return left_sum + right_sum
elif root.data == '-':
return left_sum - right_sum
elif root.data == '*':
return left_sum * right_sum
else:
return left_sum // right_sum
# Driver function to test above problem
if __name__ == '__main__':
# creating a sample tree
root = node('+')
root.left = node('*')
root.left.left = node('5')
root.left.right = node('-4')
root.right = node('-')
root.right.left = node('100')
root.right.right = node('20')
print (evaluateExpressionTree(root))
root = None
# creating a sample tree
root = node('+')
root.left = node('*')
root.left.left = node('5')
root.left.right = node('4')
root.right = node('-')
root.right.left = node('100')
root.right.right = node('/')
root.right.right.left = node('20')
root.right.right.right = node('2')
print (evaluateExpressionTree(root))
# This code is contributed by Harshit Sidhwa
C#
// C# program to evaluate expression tree
using System;
public class GFG
{
// Class to represent the nodes of syntax tree
public class Node {
public
String data;
public
Node left, right;
public Node(String d) {
data = d;
left = null;
right = null;
}
}
private static int toInt(String s) {
int num = 0;
// Check if the integral value is
// negative or not
// If it is not negative, generate
// the number normally
if (s[0] != '-')
for (int i = 0; i < s.Length; i++)
num = num * 10 + ((int) s[i] - 48);
// If it is negative, calculate the +ve number
// first ignoring the sign and invert the
// sign at the end
else {
for (int i = 1; i < s.Length; i++)
num = num * 10 + ((int) (s[i]) - 48);
num = num * -1;
}
return num;
}
// This function receives a node of the syntax
// tree and recursively evaluate it
public static int evalTree(Node root) {
// Empty tree
if (root == null)
return 0;
// Leaf node i.e, an integer
if (root.left == null && root.right == null)
return toInt(root.data);
// Evaluate left subtree
int leftEval = evalTree(root.left);
// Evaluate right subtree
int rightEval = evalTree(root.right);
// Check which operator to apply
if (root.data.Equals("+"))
return leftEval + rightEval;
if (root.data.Equals("-"))
return leftEval - rightEval;
if (root.data.Equals("*"))
return leftEval * rightEval;
return leftEval / rightEval;
}
// Driver code
public static void Main(String[] args) {
// Creating a sample tree
Node root = new Node("+");
root.left = new Node("*");
root.left.left = new Node("5");
root.left.right = new Node("-4");
root.right = new Node("-");
root.right.left = new Node("100");
root.right.right = new Node("20");
Console.WriteLine(evalTree(root));
root = null;
// Creating a sample tree
root = new Node("+");
root.left = new Node("*");
root.left.left = new Node("5");
root.left.right = new Node("4");
root.right = new Node("-");
root.right.left = new Node("100");
root.right.right = new Node("/");
root.right.right.left = new Node("20");
root.right.right.right = new Node("2");
Console.WriteLine(evalTree(root));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program to evaluate expression tree
var root;
// Class to represent the nodes of syntax tree
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
function toInt( s) {
var num = 0;
// Check if the integral value is
// negative or not
// If it is not negative, generate
// the number normally
if (s.charAt(0) != '-')
for (i = 0; i < s.length; i++)
num = num * 10 + ( s.charCodeAt(i) - 48);
// If it is negative, calculate the +ve number
// first ignoring the sign and invert the
// sign at the end
else {
for (i = 1; i < s.length; i++)
num = num * 10 + (s.charCodeAt(i) - 48);
num = num * -1;
}
return num;
}
// This function receives a node of the syntax
// tree and recursively evaluate it
function evalTree(root) {
// Empty tree
if (root == null)
return 0;
// Leaf node i.e, an integer
if (root.left == null && root.right == null)
return toInt(root.data);
// Evaluate left subtree
var leftEval = evalTree(root.left);
// Evaluate right subtree
var rightEval = evalTree(root.right);
// Check which operator to apply
if (root.data === ("+"))
return leftEval + rightEval;
if (root.data === ("-"))
return leftEval - rightEval;
if (root.data === ("*"))
return leftEval * rightEval;
return leftEval / rightEval;
}
// Driver code
// Creating a sample tree
var root = new Node("+");
root.left = new Node("*");
root.left.left = new Node("5");
root.left.right = new Node("-4");
root.right = new Node("-");
root.right.left = new Node("100");
root.right.right = new Node("20");
document.write(evalTree(root));
root = null;
// Creating a sample tree
root = new Node("+");
root.left = new Node("*");
root.left.left = new Node("5");
root.left.right = new Node("4");
root.right = new Node("-");
root.right.left = new Node("100");
root.right.right = new Node("/");
root.right.right.left = new Node("20");
root.right.right.right = new Node("2");
document.write("<br/>"+evalTree(root));
// This code is contributed by gauravrajput1
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA