Scribd
Upload
6 views6 pages

Infix to Postfix Conversion Algorithm

The document describes an algorithm for converting an infix notation mathematical expression to postfix notation. It involves the following steps: 1) Read each token from the infix expression and either push it onto an operator stack or add it to the output queue. 2) If the token is an operator, pop operators with higher precedence off the stack and onto the output queue. 3) Push the current operator onto the stack. 4) When encountering parentheses, push them and pop until their match is found. 5) When finished reading all tokens, pop all remaining operators off the stack and onto the output queue. 6) The final output queue contains the expression in postfix notation.

Uploaded by

ksarg
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views6 pages

Infix to Postfix Conversion Algorithm

The document describes an algorithm for converting an infix notation mathematical expression to postfix notation. It involves the following steps: 1) Read each token from the infix expression and either push it onto an operator stack or add it to the output queue. 2) If the token is an operator, pop operators with higher precedence off the stack and onto the output queue. 3) Push the current operator onto the stack. 4) When encountering parentheses, push them and pop until their match is found. 5) When finished reading all tokens, pop all remaining operators off the stack and onto the output queue. 6) The final output queue contains the expression in postfix notation.

Uploaded by

ksarg
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

lgorithm:(Taken from wikipedia)

While there are tokens to be read:

Read a token . If the token is a number, then add it to the output queue. If the token is a function token, then push it onto the stack. If the token is a function argument separator (e.g., a comma): Until the topmost element of the stack is a left parenthesis, pop the element from the stack and push it onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched. If the token is an operator, o1, then: while there is an operator, o2, at the top of the stack, and either

o1 is associative or left-associative and its precedence is less than (lower precedence) or equal to that of o2, or o1 is right-associative and its precedence is less than (lower precedence) that of o 2, pop o2 off the stack, onto the output queue; push o1 onto the stack.

If the token is a left parenthesis, then push it onto the stack. If the token is a right parenthesis: Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. Pop the left parenthesis from the stack, but not onto the output queue. If the token at the top of the stack is a function token, pop it and onto the output queue. If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

When there are no more tokens to read:


Exit.

While there are still operator tokens in the stack: If the operator token on the top of the stack is a parenthesis, then there are mismatched parenthesis. Pop the operator onto the output queue.

view source print? 01.#include <stdio.h> 02.#define size 10 [Link] stack[size]; [Link] tos=0,ele; [Link] push(); [Link] pop(); [Link] show(); [Link] isempty(); [Link] isfull(); [Link] infix[30],output[30]; [Link] prec(char); [Link] main() 13.{ [Link] i=0,j=0,k=0,length; [Link] temp; [Link]("\nEnter an infix expression:"); [Link]("%s",infix); [Link]("\nThe infix expresson is %s",infix); [Link]=strlen(infix); [Link](i=0;i<= prec(stack[tos-1]) )

21.{ [Link]=pop(); [Link]("\n the poped element is :%c",temp); [Link][j++]=temp; [Link](infix[i]); [Link]("\n The pushed element is :%c",infix[i]); [Link](); 28.} [Link] 30.{ [Link](infix[i]); [Link]("\nThe pushed element is:%c",infix[i]); [Link](); 34.} 35.} [Link] 37.{ [Link](infix[i]=='(') 39.{ [Link](infix[i]); [Link]("\nThe pushed-- element is:%c",infix[i]); 42.}

[Link](infix[i]==')') 44.{ [Link]=pop(); [Link](temp!='(') 47.{output[j++]=temp; [Link]("\nThe element added to Q is:%c",temp); 49.//temp=pop(); [Link]("\n the poped element is :%c",temp); [Link]=pop();} 52.} 53.} 54.} 55.} [Link]("\nthe infix expression is: %s",output); 57.} [Link](tos!=0) 59.{ [Link][j++]=pop(); 61.} [Link]("the infix expression is: %s\n",output); 63.} 64.//Functions for operations on stack

[Link] push(int ele) 66.{ [Link][tos]=ele; [Link]++; 69.} [Link] pop() 71.{ [Link]--; [Link](stack[tos]); 74.} [Link] show() 76.{ [Link] x=tos; [Link]("--The Stack elements are....."); [Link](x!=0) [Link]("%c, ",stack[--x]); 81.} 82. 83.//Function to get the precedence of an operator [Link] prec(char symbol) 85.{ [Link](symbol== '(')

[Link] 0; [Link](symbol== ')') [Link] 0; [Link](symbol=='+' || symbol=='-') [Link] 1; [Link](symbol=='*' || symbol=='/') [Link] 2; [Link](symbol=='^') [Link] 3; [Link] 0; 97.}

You might also like