Scribd
Upload
11 views6 pages

Postfix to Infix and priority queue

The document explains the process of converting a postfix expression to infix notation using a stack, detailing each step with an example. It also describes the properties and functions of a priority queue, including how to insert and delete elements based on their priority. Additionally, it outlines the time complexity for various operations related to the priority queue.

Uploaded by

Ritika Lohiya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
11 views6 pages

Postfix to Infix and priority queue

The document explains the process of converting a postfix expression to infix notation using a stack, detailing each step with an example. It also describes the properties and functions of a priority queue, including how to insert and delete elements based on their priority. Additionally, it outlines the time complexity for various operations related to the priority queue.

Uploaded by

Ritika Lohiya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 6

Postfix to Infix

Postfix to Expression Stack


Example: abc-+de-fg-h+/*
Infix abc-+de-fg-h+/* NULL
bc-+de-fg-h+/* a
c-+de-fg-h+/* ba
1.While there are input symbol left
-+de-fg-h+/* cba
1.1 Read the next symbol from the input.
+de-fg-h+/* a “b-c”
2.If the symbol is an operand de-fg-h+/* “a+b-c”
2.1 Push it onto the stack.
e-fg-h+/* d “a+b-c”

3.Otherwise, -fg-h+/* ed “a+b-c”


3.1 the symbol is an operator. fg-h+/* “d-e” “a+b-c”
3.2 Pop the top 2 values from the stack.
g-h+/* f “d-e” “a+b-c”
3.3 Put the operator, with the values as arguments and form a string.
3.4 Push the resulted string back to stack. -h+/* gf “d-e” “a+b-c”
h+/* “f-g” “d-e” “a+b-c”
4.If there is only one value in the stack +/* h “f-g” “d-e” “a+b-c”
4.1 That value in the stack is the desired infix string.
/* “f-g+h” “d-e” “a+b-c”
* “d-e”/”f-g+h” “a+b-c”
Output: (a+b-c)*(d-e)/(f-g+h) “a+b-c”*“d-e”/”f-g+h”
Priority Queue
Priority
Queue
Priority Queue is an extension of queue with following properties.
1. Every item has a priority associated with it.
2. An element with high priority is dequeued before an element with low priority.
3. If two elements have the same priority, they are served according to their order in the queue.
Priority
Queue
/* Function to insert value into priority queue */ /* Function to check priority and place element */
void insert_by_priority(int data)
{ void check(int data)
if (rear >= MAX - 1) {
{ int i,j;
printf("\n Queue overflow"); for (i = 0; i <= rear; i++)
return; {
} if (data >= pri_que[i])
if ((front == -1) && (rear == -1)) {
{ for (j = rear + 1; j > i; j--)
front++; {
rear++; pri_que[j] = pri_que[j - 1];
pri_que[rear] = data; }
return; pri_que[i] = data;
} return;
else }
check(data); }
rear++; pri_que[i] = data;
} }
Priority
Queue
/* Function to delete an element from queue */

void delete_by_priority()
{
int i; Time complexity
if ((front==-1) && (rear==-1)|| (front > rear)) Enqueue – O(?)
{
printf("\nQueue is empty no elements to delete"); Dequeue – O(?)
return; Traversal – O(?)
}
printf("Element deleted from Queue is: %d\n",pri_que[front]);
front = front + 1;
}

You might also like