INFIX TO PREFIX CONVERSION

BCA Third semester

Infix to prefix conversion

Data Structure

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define MAX 20

char stack[MAX];
int top = -1;
char pop();
void push(char item);

int prcd(char symbol) {
switch(symbol) {
case ‘+’:
case ‘-‘:
return 2;
case ‘*’:
case ‘/’:
return 4;
case ‘^’:
case ‘$’:
return 6;
case ‘(‘:
case ‘)’:
case ‘#’:
return 1;
}
}

int isoperator(char symbol) {
switch(symbol) {
case ‘+’:
case ‘-‘:
case ‘*’:
case ‘/’:
case ‘^’:
case ‘$’:
case ‘(‘:
case ‘)’:
return 1;
default:
return 0;
}
}

void convertip(char infix[],char prefix[]) {
int i,symbol,j=0;
char test[MAX];

infix=strrev(infix);
stack[++top]=’#’;

for(i=0;iprcd(stack[top])) {
push(symbol);
}else {
while(prcd(symbol)<=prcd(stack[top])) {
prefix[j]=pop();
j++;
}
push(symbol);
}//end of else.
}//end of else.
}//end of else.
}//end of for.

while(stack[top]!=’#’) {
prefix[j]=pop();
j++;
}
prefix[j]=’\0′;//null terminate string.
prefix=strrev(prefix);
}

int main() {
char infix[20],prefix[20];
clrscr();
printf(“Enter the valid infix string : “);
gets(infix);
convertip(infix,prefix);
printf(“The corresponding prefix string is : “);
puts(prefix);
getch();
return 0;
}

void push(char item) {
top++;
stack[top]=item;
}

char pop() {
char a;
a=stack[top];
top–;
return a;
}

INPUT
Enter the valid infix string : (a+b)*(c-d)

OUTPUT
The corresponding prefix string is : *+ab-cd

Next Program

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
#include <sstream>

int prec(char input);

using namespace std;

int main()
{
	std::string final_string;
	std::string input_string;
	std::stack <char> expression_stack;

	// "(1 + ((2 + 3) * (4 * 5)))"
	cout << "Please enter an expression (For example, a + b - c)" << endl;
	cout << "Enter an expression : "; getline(cin, input_string);
	cout << "The prefix expression : ";
	{
		std::stringstream cout;

		int i = 0;
		while(i < input_string.size())
		{
			char input = input_string[i];

			if((input >= '0' && input <= '9') || (input >= 'a' && input <= 'z') || (input >= 'A' && input <= 'Z'))
			{
				cout << input << ' ';		
			}
			else if(input == '(')
			{
				expression_stack.push(input);		
			}
			else if(input == ')')
			{
				while(!expression_stack.empty() && expression_stack.top() != '(')
				{
					cout << expression_stack.top() << ' ';
					expression_stack.pop();
				}

				if(!expression_stack.empty()) expression_stack.pop();
				else
				{
					cout << endl;
					cerr << "Error : No matching '(' token" << endl; cin.get(); return 100;
				}
			}
			else if(input == '*' || input == '/' || input == '+' || input == '-')
			{
				if(expression_stack.empty() || prec(expression_stack.top()) < prec(input))
				{
					expression_stack.push(input);
				}
				else
				{
					while(!expression_stack.empty())
					{
						if(prec(expression_stack.top()) < prec(input)) break;
						
						cout << expression_stack.top() << ' ';
						expression_stack.pop();
					}

					expression_stack.push(input);
				}
			}
			else if(input_string[i] != ' ')
			{
				cout << endl;
				cerr << "Error : Invalid character or token : '" << input << "'" << endl; cin.get(); return 100;
			}	

			i++;
		}

		while(!expression_stack.empty())
		{
			cout << expression_stack.top() << ' ';
			expression_stack.pop();
		}

		final_string = cout.str();
		std::reverse(final_string.begin(), final_string.end());
	}

	cout << final_string;
	cout << endl;

	return 0;
}

// Returns a precedence value for a certain operator
// Lowest : (
// Normal : + -
// Highest : * /
int prec(char input)
{
	int precedence_input;
	if(input == '(') precedence_input = 0;
	else 
	{
		if(input == '+' || input == '-') precedence_input = 1;
		else
		{
			if(input == '*' || input == '/') precedence_input = 2;	
			else
			{
				cout << endl;
				cerr << "Error : Invalid input operator : " << input << endl; cin.get(); exit(100);
			}
		}
	}

	return precedence_input;
}

• install our bcanotesnepal  application from the play store:  BCA Notes NepalDo does not forget to like our Facebook page: www.facebook.com/bcanotesnepal
  Facebook Groups  https://www.facebook.com/groups/bcanotesnepal
  Join In our Facebook Group https://www.facebook.com/groups/1200219363518714/

if you need a Downloadable link once message us on-page you can get at a time.

m.me/bcanotesnepal

This post is posted for not further third-party purposes.

Copyright By:-  Bcanotesneapl

Not allowed to upload these notes to other sites.

Like our Facebook Page https://www.facebook.com/bcanotesnepal/

if you want to download this PDF comment on us we will provide you a downloadable link.

if you like please share this post with your friend who studies in BCA

if you have any query please comment below,

if you like our sites. you can visit again for the latest updates notes of different BCA subjects of Presentation and different topics with assignment questions and solutions.

Don’t forget to like our page and post also share with your friend and having your group.

if you have any questions you can drop or share them with me using the comment box I will try to answer your question.

Like our Facebook Page https://www.facebook.com/bcanotesnepal/