Vrednotenje izraznega drevesa
Glede na preprosto izrazno drevo sestavljen iz osnovnih binarnih operatorjev, tj. + - * in / ter nekaterih celih števil, ki ovrednotijo izrazno drevo.
Primeri:
Priporočena praksa Izrazno drevo Poskusite!Vnos: Korensko vozlišče spodnjega drevesa
Izhod: 100
Vnos: Korensko vozlišče spodnjega drevesa
Izhod: 110
Pristop: Pristop k reševanju tega problema temelji na naslednjem opazovanju:
Ker so vsi operaterji v drevesu binarni, bo imelo vsako vozlišče 0 ali 2 otroka. Kot je mogoče sklepati iz zgornjih primerov, bi se vse cele vrednosti pojavile na vozliščih listov, medtem ko notranja vozlišča predstavljajo operaterje.
Zato lahko storimo neurejeno prečkanje binarnega drevesa in ovrednotite izraz, ko se premikamo naprej.
Za ovrednotenje skladenjskega drevesa lahko sledimo rekurzivnemu pristopu.
Algoritem:
- Naj bo t skladenjsko drevo
- Če t ni nič, potem
- Če je t.info operand, potem
- Vrnitev t.info
- drugače
- A = reši (t.levo)
- B = reši (t.desno)
- return A operator B, kjer je operator informacija v t
Spodaj je izvedba zgornjega pristopa:
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>
Izhod
60 110
Časovna zapletenost: O(n), saj je vsako vozlišče obiskano enkrat.
Pomožni prostor: O(n)
