Evaluatie van expressieboom
Gegeven een simpele expressie boom bestaande uit binaire basisoperatoren, d.w.z. + - * en/en enkele gehele getallen evalueren de expressieboom.
Voorbeelden:
Aanbevolen praktijk Expressieboom Probeer het!Invoer: Wortelknooppunt van de onderstaande boom
Uitgang: 100
Invoer: Wortelknooppunt van de onderstaande boom
Uitgang: 110
Benadering: De aanpak om dit probleem op te lossen is gebaseerd op de volgende observatie:
Omdat alle operatoren in de boom binair zijn, heeft elk knooppunt 0 of 2 kinderen. Zoals uit de bovenstaande voorbeelden kan worden afgeleid, verschijnen alle gehele waarden op de bladknooppunten, terwijl de interne knooppunten de operators vertegenwoordigen.
Daarom kunnen wij het doen inorder doorkruisen van de binaire boom en evalueer de uitdrukking terwijl we verder gaan.
Om de syntaxisboom te evalueren kan een recursieve benadering worden gevolgd.
Algoritme:
- Laat t de syntaxisboom zijn
- Als t niet nul is, dan
- Als t.info operand is dan
- Retourneer t.info
- Anders
- A = oplossen(t.links)
- B = oplossen(t.right)
- return A operator B waarbij operator de informatie in t is
Hieronder vindt u de implementatie van de bovenstaande aanpak:
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>
Uitvoer
60 110
Tijdcomplexiteit: O(n) aangezien elk knooppunt één keer wordt bezocht.
Hulpruimte: Op)
