TRAKLA2 - Infix to Postfix

Infix to Postfix

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions Infix expressions are often translated into postfix form in which the operators appear after their operands. The advantage of the postfix notation is that it eliminates the parenthesis of the infix notation without violating the original semantics. Transform the Infix expression into a Postfix expression using the stack as an auxiliary structure. Use the algorithm below. Some addditional problems. Note that in this exercise, the stack is implemented by utilizing a linked list in which the new item is always inserted (and deleted) into (from) the beginning of the linked list. In addition, the output is a linked list as well. However, new items are inserted at the end of the list (due to the fact that we do not want to reverse the order of the output items). You can drag & drop elements from the input array to the stack, from the input array to the output array and from the stack to the output array. In addition, an element can be popped from the stack without inserting it anywhere by just dropping it into any empty area (i.e., while eliminating left parenthesis from the stack). Note that right parenthesis do not need any GUI operation as it''s only read, but never written anywhere.
infix-postfix 1. Scan the Infix Expression from left to right. 2. If the scannned character is an operand, copy it to the Postfix Expression. 3. If the scanned character is left parentheses, push it onto the stack. 4. If the scanned character is right parenthesis, the symbol at the top of the stack is popped off the stack and copied to the Postfix Expression. Repeat until the symbol at the top of the stack is a left parenthesis (both parentheses are discarded in this process). 5. If the scanned character is an operator and has a higher precedence than the symbol at the top of the stack, push it onto the stack. 6. If the scanned character is an operator and the precedence is lower than or equal to the precedence of the operator at the top of the stack, one element of the stack is popped to the Postfix Expression; repeat this step with the new top element on the stack. Finally, push the scanned character onto the stack. 7. After all characters are scanned, the stack is popped to the Postfix Expression until the stack is empty.