Avaluació de l'arbre d'expressió
Donat un simple arbre d'expressió que consisteix en operadors binaris bàsics, és a dir, + - * i / i alguns nombres enters avaluen l'arbre d'expressió.
Exemples:
Pràctica recomanada Arbre d'expressions Prova-ho!Entrada: Node arrel de l'arbre de sota
Sortida: 100
Entrada: Node arrel de l'arbre de sota
Sortida: 110
Enfocament: L'enfocament per resoldre aquest problema es basa en la següent observació:
Com que tots els operadors de l'arbre són binaris, cada node tindrà 0 o 2 fills. Com es pot inferir dels exemples anteriors, tots els valors enters apareixeran als nodes fulla mentre que els nodes interiors representen els operadors.
Per tant ho podem fer travessa en ordre de l'arbre binari i avaluar l'expressió a mesura que avancem.
Per avaluar l'arbre de sintaxi es pot seguir un enfocament recursiu.
Algorisme:
- Sigui t l'arbre de sintaxi
- Si t no és nul, aleshores
- Si t.info és operand, aleshores
- Torna t.info
- Altrament
- A = resoldre (t.esquerra)
- B = resoldre (t.dreta)
- retorna un operador B on l'operador és la informació continguda a t
A continuació es mostra la implementació de l'enfocament anterior:
C++ // C++ program to evaluate an expression tree #include 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 ( '
' + evalTree ( root )); // This code is contributed by gauravrajput1 < /script>
Sortida
60 110
Complexitat temporal: O(n) ja que cada node es visita una vegada.
Espai auxiliar: O(n)
