What is INFIX Expression? When you write an arithmetic exression such as B * C, the form of the expression provides you with information so that you can interpret it correctly. In this case we know that the variable B is being multiplied by the variable C since the multiplication operator * appears between them in the expression. This type of notation is referred to as infix since the operator is in between the two operands that it is working on. What is POSTFIX Expression? Postfix requires that its operators come after the corresponding operands. Steps for Conversion:- We need to develop an algorithm to convert any infix expression to a postfix expression. To do this we will look closer at the conversion process. Consider once again the expression A + B * C. As shown above, A B C * + is the postfix equivalent. We have already noted that the operands A, B, and C stay in their relative positions. It is only the operators that change position. Let’s look again at the operators in the infix expression. The first operator that appears from left to right is +. However, in the postfix expression, + is at the end since the next operator, *, has precedence over addition. The order of the operators in the original expression is reversed in the resulting postfix expression. As we process the expression, the operators have to be saved somewhere since their corresponding right operands are not seen yet. Also, the order of these saved operators may need to be reversed due to their precedence. This is the case with the addition and the multiplication in this example. Since the addition operator comes before the multiplication operator and has lower precedence, it needs to appear after the multiplication operator is used. Because of this reversal of order, it makes sense to consider using a stack to keep the operators until they are needed. What about (A + B) * C? Recall that A B + C * is the postfix equivalent. Again, processing this infix expression from left to right, we see + first. In this case, when we see *, + has already been placed in the result expression because it has precedence over * by virtue of the parentheses. We can now start to see how the conversion algorithm will work. When we see a left parenthesis, we will save it to denote that another operator of high precedence will be coming. That operator will need to wait until the corresponding right parenthesis appears to denote its position (recall the fully parenthesized technique). When that right parenthesis does appear, the operator can be popped from the stack. As we scan the infix expression from left to right, we will use a stack to keep the operators. This will provide the reversal that we noted in the first example. The top of the stack will always be the most recently saved operator. Whenever we read a new operator, we will need to consider how that operator compares in precedence with the operators, if any, already on the stack. Assume the infix expression is a string of tokens delimited by spaces. The operator tokens are *, /, +, and -, along with the left and right parentheses, ( and ). The operand tokens are the single-character identifiers A, B, C, and so on. The following steps will produce a string of tokens in postfix order. Create an empty stack called opstack for keeping operators. Create an empty list for output.
0 Comments
Description:
Department of computer engineering has Student's Club named As 'Pinnacle Club'. Students of Second, Third and Final Year of department can be granted membership on request. Similarly, one may cancel the membership of the Club. Here is C++ program to maintain Club Members Information using Singly Linked List. We are creating two separate lists for Division A and Division B. The list contains Student PRN and Name. Here, 'header1' stores address of A division list and 'header2' stores address of B division list. The following functions perform respective operations on list: 1. create() - It creates the initial list in which first node and last represent President and Secretary respectively. 2. count() - It counts the total number of members including President and Secretary in list. 3. add() - It is used to more members in list. 4. del() - It is used to remove any member from list. 5. display() - It simply displays the list i.e from President to Secretary. 6. rdisplay() - It displays list in reverse manner i.e from Secretary to President using Recursion. 7. concatinate() - It can concatinate lists of division A and division B. |
AuthorProf. Ketan Sanjay Desale Archives
April 2020
Categories |