Infix to Postfix

/* C++ implementation to convert infix expression to postfix*/

// Note that here we use std::stack for Stack operations
#include<bits/stdc++.h>
using namespace std;

//Function to return precedence of operators

int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}

// The main function to convert infix expression

//to postfix expression
void infixToPostfix(string s)
{
std::stack<char> st;
st.push('N');
int l = s.length();
string ns;
for(int i = 0; i < l; i++)
{
// If the scanned character is an operand, add it to output string.
if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z'))
ns+=s[i];

// If the scanned character is an ‘(‘, push it to the stack.

else if(s[i] == '(')

st.push('(');

// If the scanned character is an ‘)’, pop and to output string from

the stack
// until an ‘(‘ is encountered.
else if(s[i] == ')')
{
while(st.top() != 'N' && st.top() != '(')
{
char c = st.top();
st.pop();
ns += c;
}
if(st.top() == '(')
{
char c = st.top();
st.pop();
}
 }

//If an operator is scanned

else{
while(st.top() != 'N' && prec(s[i]) <= prec(st.top()))
{
char c = st.top();
st.pop();
ns += c;
}
st.push(s[i]);
}

}
//Pop all the remaining elements from the stack
while(st.top() != 'N')
{
char c = st.top();
st.pop();
ns += c;
}

cout << ns << endl;

//Driver program to test above functions

int main()
{
string exp = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
return 0;
}

Output:
abcd^e-fgh*+^*+i-

evaluation of postfix expression

Postfix Evaluation using C++ Stack

Any equation in the form "5 + ((1 + 2) × 4) − 3" is called Infix expression. The postfix expression of

this infix notation will be: "5 1 2 + 4 × + 3 −". It is also known as Reverse Polish notation.
Algorithm:

 Scan input expression from left to right

o If scanned input is an operand, push it into the stack
o If scanned input is an operator, pop out two values from stack. Then, perform
operation between popped values and then push back the result into the stack.

 Repeat above two steps till all the characters are scanned.
 After all characters are scanned, there will be only one element in the stack, and this is the
result of given expression.

C++ Implementation:
The following program evaluates a given postfix string. The numbers in inputs must be space

separated:

/*
* Postfix Evaluation
* Language: C++
*/

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <stack>
#include <string.h>

using namespace std;

bool isOperator(char ch)

{
if (ch=='+' || ch=='-' || ch=='*' || ch=='/')
return true;
else
return false;
}

int performOperation(int op1, int op2, char op)

{
int ans;
switch(op){
case '+':
ans = op2 + op1;
break;
case '-':
ans = op2 - op1;
break;
case '*':
 ans = op2 * op1;
break;
case '/':
ans = op2 / op1;
break;
}
return ans;
}

int main()
{
char exp[1000], buffer[15];
int i,op1, op2, len, j, x;
stack<int> s;
printf("Enter a Postfix Expression: ( e.g. 23 34 * )\n");
gets(exp);
len = strlen(exp);
j = 0;
for(i=0; i<len;i++){

if(exp[i]>='0' && exp[i]<='9'){

buffer[j++] = exp[i];
}
else if(exp[i]==' '){
if(j>0){
buffer[j] = '\0';
x = atoi(buffer);
s.push(x);
j = 0;
}
}

else if(isOperator(exp[i])){
op1 = s.top();
s.pop();
op2 = s.top();
s.pop();
s.push(performOperation(op1, op2, exp[i]));
}
}

printf("Answer is %d\n", s.top());

return 0;
}

Insertion sort

#include<iostream>

using namespace std;

int main()
{
int i,j,n,temp,a[30];
cout<<"Enter the number of elements:";
 cin>>n;
cout<<"\nEnter the elements\n";

for(i=0;i<n;i++)
{
cin>>a[i];
}

for(i=1;i<=n-1;i++)
{
temp=a[i];
j=i-1;

while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j]; //moves element forward
j=j-1;
}

a[j+1]=temp; //insert element in proper place

}

cout<<"\nSorted list is as follows\n";

for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}

return 0;
}

Selection Sort

#include <iostream>

using namespace std;

// Sort arr[] of size n using Selection Sort.

void SelectionSort (int arr[], int n)
{
int i, j;
for (i = 0; i < n; ++i)
{
for (j = i+1; j < n; ++j)
{
// Comparing consecutive data and switching values if value
at i > j.
if (arr[i] > arr[j])
{
 arr[i] = arr[i]+arr[j];
arr[j] = arr[i]-arr[j];
arr[i] = arr[i]-arr[j];
}
}
// Value at i will be minimum of all the values above this index.
}
}

int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;

int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}

SelectionSort(arr, n);

// Display the sorted data.

cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];

return 0;
}

Binary Search

#include <iostream>
using namespace std;

int main()
{
int count, i, arr[30], num, first, last, middle;
cout<<"how many elements would you like to enter?:";
cin>>count;

for (i=0; i<count; i++)

{
cout<<"Enter number "<<(i+1)<<": ";
cin>>arr[i];
}
cout<<"Enter the number that you want to search:";
cin>>num;
first = 0;
last = count-1;
middle = (first+last)/2;
 while (first <= last)
{
if(arr[middle] < num)
{
first = middle + 1;

}
else if(arr[middle] == num)
{
cout<<num<<" found in the array at the location "<<middle+1<<"\n";
break;
}
else {
last = middle - 1;
}
middle = (first + last)/2;
}
if(first > last)
{
cout<<num<<" not found in the array";
}
return 0;
}
Output:

how many elements would you like to enter?:5

Enter number 1: 12
Enter number 2: 45
Enter number 3: 8
Enter number 4: 9
Enter number 5: 100
Enter the number that you want to search:8
8 found in the array at the location 3

Linear Search

#include<iostream>

using namespace std;

int main()

int a[20],n,x,i,flag=0;

cout<<"How many elements?";

 cin>>n;

cout<<"\nEnter elements of the array\n";

for(i=0;i<n;++i)

cin>>a[i];

cout<<"\nEnter element to search:";

cin>>x;

for(i=0;i<n;++i)

if(a[i]==x)

flag=1;

break;

if(flag)

cout<<"\nElement is found at position "<<i+1;

else

cout<<"\nElement not found";

return 0;

}
 Output
How many elements?4
Enter elements of the array
5 9 12 4
Enter element to search:9
Element is found at position 2

Bubble Sort

#include<iostream>

using namespace std;

int main()

int a[50],n,i,j,temp;

cout<<"Enter the size of array: ";

cin>>n;

cout<<"Enter the array elements: ";

for(i=0;i<n;++i)

cin>>a[i];

for(i=1;i<n;++i)

for(j=0;j<(n-i);++j)

if(a[j]>a[j+1])

temp=a[j];
 a[j]=a[j+1];

a[j+1]=temp;

cout<<"Array after bubble sort:";

for(i=0;i<n;++i)

cout<<" "<<a[i];

return 0;

Output

Heap Sort

// C++ program for implementation of Heap Sort

#include <iostream>

using namespace std;

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2

// If left child is larger than root

 if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root

if (largest != i)
{
swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);
}
}

// main function to do heap sort

void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// One by one extract an element from heap

for (int i=n-1; i>=0; i--)
{
// Move current root to end
swap(arr[0], arr[i]);

// call max heapify on the reduced heap

heapify(arr, i, 0);
}
}

/* A utility function to print array of size n */

void printArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
cout << "\n";
}

// Driver program
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);

heapSort(arr, n);

cout << "Sorted array is \n";

printArray(arr, n);
}
 Output:
Sorted array is
5 6 7 11 12 13

Quick Sort

Program for Quick Sort in C++

#include <iostream>

using namespace std;

void quick_sort(int[],int,int);

int partition(int[],int,int);

int main()

int a[50],n,i;

cout<<"How many elements?";

 cin>>n;

cout<<"\nEnter array elements:";

for(i=0;i<n;i++)

cin>>a[i];

quick_sort(a,0,n-1);

cout<<"\nArray after sorting:";

for(i=0;i<n;i++)

cout<<a[i]<<" ";

return 0;

void quick_sort(int a[],int l,int u)

int j;
 if(l<u)

j=partition(a,l,u);

quick_sort(a,l,j-1);

quick_sort(a,j+1,u);

int partition(int a[],int l,int u)

int v,i,j,temp;

v=a[l];

i=l;

j=u+1;

do

do
 i++;

while(a[i]<v&&i<=u);

do

j--;

while(v<a[j]);

if(i<j)

temp=a[i];

a[i]=a[j];

a[j]=temp;

}while(i<j);

a[l]=a[j];

a[j]=v;
 return(j);

Output
How many elements?6
Enter array elements:9 15 6 7 10 12
Array after sorting:6 7 9 10 12 15