logging in or signing up e computer notes - Data Structures - 7 ecomputernotes Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 10 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: December 28, 2011 This Presentation is Public Favorites: 0 Presentation Description Computer Notes on all computer subject that's related to all university and all college.it help you prepare better for the school and college exams ecomputernotes present to you the revision notes on Computer subjects. Comments Posting comment... Premium member Presentation Transcript PowerPoint Presentation: Class No.07 Data Structures http://ecomputernotes.comInfix to Postfix: Infix to Postfix Infix Postfix A + B A B + 12 + 60 – 23 12 60 + 23 – (A + B)*(C – D ) A B + C D – * A B * C – D + E/F A B C*D – E F/+ http://ecomputernotes.comInfix to Postfix: Infix to Postfix Note that the postfix form an expression does not require parenthesis. Consider ‘4+3*5’ and ‘(4+3)*5’. The parenthesis are not needed in the first but they are necessary in the second. The postfix forms are: 4+3*5 435*+ (4+3)*5 43+5* http://ecomputernotes.comEvaluating Postfix : Evaluating Postfix Each operator in a postfix expression refers to the previous two operands. Each time we read an operand, we push it on a stack. When we reach an operator, we pop the two operands from the top of the stack, apply the operator and push the result back on the stack. http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Stack s; while( not end of input ) { e = get next element of input if( e is an operand ) s.push( e ); else { op2 = s.pop(); op1 = s.pop(); value = result of applying operator ‘e’ to op1 and op2; s.push( value ); } } finalresult = s.pop(); http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 2 1 7 7 7,2 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 2 1 7 7 7,2 7 2 49 49 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 2 1 7 7 7,2 7 2 49 49 3 7 2 49 49,3 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 2 1 7 7 7,2 7 2 49 49 3 7 2 49 49,3 + 49 3 52 52 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 2 1 7 7 7,2 7 2 49 49 3 7 2 49 49,3 + 49 3 52 52 http://ecomputernotes.comConverting Infix to Postfix: Converting Infix to Postfix Consider the infix expressions ‘A+B*C’ and ‘ (A+B)*C’. The postfix versions are ‘ABC*+’ and ‘AB+C*’. The order of operands in postfix is the same as the infix. In scanning from left to right, the operand ‘A’ can be inserted into postfix expression. http://ecomputernotes.comConverting Infix to Postfix: Converting Infix to Postfix The ‘+’ cannot be inserted until its second operand has been scanned and inserted. The ‘+’ has to be stored away until its proper position is found. When ‘B’ is seen, it is immediately inserted into the postfix expression. Can the ‘+’ be inserted now? In the case of ‘A+B*C’ cannot because * has precedence. http://ecomputernotes.comConverting Infix to Postfix: Converting Infix to Postfix In case of ‘(A+B)*C’, the closing parenthesis indicates that ‘+’ must be performed first. Assume the existence of a function ‘prcd(op1,op2)’ where op1 and op2 are two operators. Prcd(op1,op2) returns TRUE if op1 has precedence over op2, FASLE otherwise.Converting Infix to Postfix: Converting Infix to Postfix prcd(‘*’,’+’) is TRUE prcd(‘+’,’+’) is TRUE prcd(‘+’,’*’) is FALSE Here is the algorithm that converts infix expression to its postfix form. The infix expression is without parenthesis.Converting Infix to Postfix: Converting Infix to Postfix Stack s; While( not end of input ) { c = next input character; if( c is an operand ) add c to postfix string; else { while( !s.empty() && prcd(s.top(),c) ){ op = s.pop(); add op to the postfix string; } s.push( c ); } while( !s.empty() ) { op = s.pop(); add op to postfix string; }Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A AConverting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A +Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A + B AB +Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A + B AB + * AB + *Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A + B AB + * AB + * C ABC + *Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A + B AB + * AB + * C ABC + * ABC * +Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A + B AB + * AB + * C ABC + * ABC * + ABC * +Converting Infix to Postfix: Converting Infix to Postfix Handling parenthesis When an open parenthesis ‘(‘ is read, it must be pushed on the stack. This can be done by setting prcd(op,‘(‘ ) to be FALSE. Also, prcd( ‘(‘,op ) == FALSE which ensures that an operator after ‘(‘ is pushed on the stack.Converting Infix to Postfix: Converting Infix to Postfix When a ‘)’ is read, all operators up to the first ‘(‘ must be popped and placed in the postfix string. To do this, prcd( op,’)’ ) == TRUE. Both the ‘(‘ and the ‘)’ must be discarded: prcd( ‘(‘,’)’ ) == FALSE. Need to change line 11 of the algorithm.Converting Infix to Postfix: Converting Infix to Postfix if( s.empty() || symb != ‘)’ ) s.push( c ); else s.pop(); // discard the ‘(‘ prcd( ‘(‘, op ) = FALSE for any operator prcd( op, ‘)’ ) = FALSE for any operator other than ‘)’ prcd( op, ‘)’ ) = TRUE for any operator other than ‘(‘ prcd( ‘)’, op ) = error for any operator. You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
e computer notes - Data Structures - 7 ecomputernotes Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 10 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: December 28, 2011 This Presentation is Public Favorites: 0 Presentation Description Computer Notes on all computer subject that's related to all university and all college.it help you prepare better for the school and college exams ecomputernotes present to you the revision notes on Computer subjects. Comments Posting comment... Premium member Presentation Transcript PowerPoint Presentation: Class No.07 Data Structures http://ecomputernotes.comInfix to Postfix: Infix to Postfix Infix Postfix A + B A B + 12 + 60 – 23 12 60 + 23 – (A + B)*(C – D ) A B + C D – * A B * C – D + E/F A B C*D – E F/+ http://ecomputernotes.comInfix to Postfix: Infix to Postfix Note that the postfix form an expression does not require parenthesis. Consider ‘4+3*5’ and ‘(4+3)*5’. The parenthesis are not needed in the first but they are necessary in the second. The postfix forms are: 4+3*5 435*+ (4+3)*5 43+5* http://ecomputernotes.comEvaluating Postfix : Evaluating Postfix Each operator in a postfix expression refers to the previous two operands. Each time we read an operand, we push it on a stack. When we reach an operator, we pop the two operands from the top of the stack, apply the operator and push the result back on the stack. http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Stack s; while( not end of input ) { e = get next element of input if( e is an operand ) s.push( e ); else { op2 = s.pop(); op1 = s.pop(); value = result of applying operator ‘e’ to op1 and op2; s.push( value ); } } finalresult = s.pop(); http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 2 1 7 7 7,2 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 2 1 7 7 7,2 7 2 49 49 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 2 1 7 7 7,2 7 2 49 49 3 7 2 49 49,3 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 2 1 7 7 7,2 7 2 49 49 3 7 2 49 49,3 + 49 3 52 52 http://ecomputernotes.comEvaluating Postfix: Evaluating Postfix Evaluate 6 2 3 + - 3 8 2 / + * 2 3 + Input op1 op2 value stack 6 6 2 6,2 3 6,2,3 + 2 3 5 6,5 - 6 5 1 1 3 6 5 1 1,3 8 6 5 1 1,3,8 2 6 5 1 1,3,8,2 / 8 2 4 1,3,4 + 3 4 7 1,7 * 1 7 7 7 2 1 7 7 7,2 7 2 49 49 3 7 2 49 49,3 + 49 3 52 52 http://ecomputernotes.comConverting Infix to Postfix: Converting Infix to Postfix Consider the infix expressions ‘A+B*C’ and ‘ (A+B)*C’. The postfix versions are ‘ABC*+’ and ‘AB+C*’. The order of operands in postfix is the same as the infix. In scanning from left to right, the operand ‘A’ can be inserted into postfix expression. http://ecomputernotes.comConverting Infix to Postfix: Converting Infix to Postfix The ‘+’ cannot be inserted until its second operand has been scanned and inserted. The ‘+’ has to be stored away until its proper position is found. When ‘B’ is seen, it is immediately inserted into the postfix expression. Can the ‘+’ be inserted now? In the case of ‘A+B*C’ cannot because * has precedence. http://ecomputernotes.comConverting Infix to Postfix: Converting Infix to Postfix In case of ‘(A+B)*C’, the closing parenthesis indicates that ‘+’ must be performed first. Assume the existence of a function ‘prcd(op1,op2)’ where op1 and op2 are two operators. Prcd(op1,op2) returns TRUE if op1 has precedence over op2, FASLE otherwise.Converting Infix to Postfix: Converting Infix to Postfix prcd(‘*’,’+’) is TRUE prcd(‘+’,’+’) is TRUE prcd(‘+’,’*’) is FALSE Here is the algorithm that converts infix expression to its postfix form. The infix expression is without parenthesis.Converting Infix to Postfix: Converting Infix to Postfix Stack s; While( not end of input ) { c = next input character; if( c is an operand ) add c to postfix string; else { while( !s.empty() && prcd(s.top(),c) ){ op = s.pop(); add op to the postfix string; } s.push( c ); } while( !s.empty() ) { op = s.pop(); add op to postfix string; }Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A AConverting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A +Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A + B AB +Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A + B AB + * AB + *Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A + B AB + * AB + * C ABC + *Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A + B AB + * AB + * C ABC + * ABC * +Converting Infix to Postfix: Converting Infix to Postfix Example: A + B * C symb postfix stack A A + A + B AB + * AB + * C ABC + * ABC * + ABC * +Converting Infix to Postfix: Converting Infix to Postfix Handling parenthesis When an open parenthesis ‘(‘ is read, it must be pushed on the stack. This can be done by setting prcd(op,‘(‘ ) to be FALSE. Also, prcd( ‘(‘,op ) == FALSE which ensures that an operator after ‘(‘ is pushed on the stack.Converting Infix to Postfix: Converting Infix to Postfix When a ‘)’ is read, all operators up to the first ‘(‘ must be popped and placed in the postfix string. To do this, prcd( op,’)’ ) == TRUE. Both the ‘(‘ and the ‘)’ must be discarded: prcd( ‘(‘,’)’ ) == FALSE. Need to change line 11 of the algorithm.Converting Infix to Postfix: Converting Infix to Postfix if( s.empty() || symb != ‘)’ ) s.push( c ); else s.pop(); // discard the ‘(‘ prcd( ‘(‘, op ) = FALSE for any operator prcd( op, ‘)’ ) = FALSE for any operator other than ‘)’ prcd( op, ‘)’ ) = TRUE for any operator other than ‘(‘ prcd( ‘)’, op ) = error for any operator.