Write a java program that implements stack ADT converts infix expression to postfix form evaluates the postfix expression?

Answer 1

// made by vijay NITJ

#include<iostream.h>

#include<string.h>

#include<stdio.h>

#include<math.h>

int precedence(char);

void main()

{

char q[20];

char p[20];

char stack[20];

int tp=-1,ts=0;

stack[0]='(';

cout<<stack;

int i=0, f=1;

cout<<"enter the prefix expression ";

gets(q);

int l=strlen(q);

q[l]=')';

while(ts!=-1)

{

if(q[i]>=47 && q[i]<=58 q[i]<=65 && q[i]<=90 q[i]<=97 && q[i]>=122)

{

p[++tp]=q[i];

}

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

stack[++ts]=q[i];

else if(q[i]=='+' q[i]=='-' q[i]=='*' q[i]=='/')

{

if(stack[ts]=='(')

stack[++ts]=q[i];

else

{

while(stack[ts]!='(')

{

int p1=precedence(q[i]);

int p2=precedence(stack[ts]);

if(p2>=p1)

p[++tp]=stack[ts--];

else

{

f=0;

break;

}

}

if(f==0)

stack[++ts]=q[i];

}

}

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

{

while(stack[ts]!='(')

{

p[++tp]=stack[ts--];

}

ts--;

}

i++;

}

for(int j=0; j<=tp;j++)

{

cout<<p[j];

}

//precedence program

int precedence(char a)

{

if(a=='+' a=='-')

return 1;

else if(a=='*' a=='/')

return 2;

}

Answer 2

/**

* @(#)ConvterPostfixToinfix.java

* project NO 1

* @version 1.00 2009/5/5 Beta

*/

import java.awt.*;

import javax.swing.*;

public class ConvterPostfixToinfix {

private CharStack Opr;

private String StPostfix="",StInfix;

public ConvterPostfixToinfix(int size) {

Opr=new CharStack(size);

}

public void Postfix(String StInfix)

{

char ch;

if(StInfix.charAt(0)=='-')

{

StPostfix+=StInfix.charAt(0);

StInfix=StInfix.substring(1);

}

else if(StInfix.charAt(0)=='+')

StInfix=StInfix.substring(1);

for (int i = 0; i

{

ch=StInfix.charAt(i);

switch(ch){

case '(':

Opr.Push(ch);

break; // lift arch

case ')':

RightArch();

break;//right arch

case '+':

case '-':

Oprator(ch,1);

break;//op+ or -

case '*':

case '/':

Oprator(ch,2);

break;//op * or /

default :StPostfix+=ch;

break;//number

}

}

while(!Opr.isEmptey()){

StPostfix+=Opr.Pop();

}

JOptionPane.showMessageDialog(null,"After conversion : "+StPostfix);

}//method

private void RightArch()

{

while(!Opr.isEmptey())

{

char local=Opr.Pop();

if(local=='(')

break;

else

StPostfix+=local;

}

}

private void Oprator(char OpIn,int opin)

{

while(!Opr.isEmptey())

{

char Top=Opr.Pop();

if(Top=='(')

{

Opr.Push(Top);

break;

}

else

{

int opTop=(Top=='+'Top=='-')?1:2;

if(opTop

{

Opr.Push(Top);

break;

}

else

StPostfix+=Top;

}//else

}

Opr.Push(OpIn);

}

}

//This Main Method

public static void main (String[] args) {

String StInfix =JOptionPane.showInputDialog("Enter Math Eqution ");

ConvterPostfixToinfix ob=new ConvterPostfixToinfix(StInfix.length());

ob.Postfix(StInfix);

}

// This Stack

public class CharStack {

private int top=-1;

private char []array;

public CharStack(int size) {

array= new char[size];

}

public boolean isEmptey()

{

return (top==-1);

}

public boolean isFull()

{

return (top==array.length-1);

}

public void Push(char o)

{

if(!isFull())

array[++top]=o;

}

public char Pop()

{

return array[top--];

}

}

Answer 3

Infix Expression :

Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.

Postfix Expression :

The Postfix(Postorder) form of the above expression is "23*45/-".

Infix to Postfix Conversion :

In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows :

• Scan the Infix string from left to right.
• Initialise an empty stack.
• If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack.
  • If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
  Repeat this step till all the characters are scanned.
• (After all characters are scanned, we have to add any character that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.
• Return the Postfix string.

Example :

Let us see how the above algorithm will be imlemented using an example.

Infix String : a+b*c-d

Initially the Stack is empty and our Postfix string has no characters. Now, the first character scanned is 'a'. 'a' is added to the Postfix string. The next character scanned is '+'. It being an operator, it is pushed to the stack.

Stack

Postfix String

Next character scanned is 'b' which will be placed in the Postfix string. Next character is '*' which is an operator. Now, the top element of the stack is '+' which has lower precedence than '*', so '*' will be pushed to the stack.

Stack

Postfix String

The next character is 'c' which is placed in the Postfix string. Next character scanned is '-'. The topmost character in the stack is '*' which has a higher precedence than '-'. Thus '*' will be popped out from the stack and added to the Postfix string. Even now the stack is not empty. Now the topmost element of the stack is '+' which has equal priority to '-'. So pop the '+' from the stack and add it to the Postfix string. The '-' will be pushed to the stack.

Stack

Postfix String

Next character is 'd' which is added to Postfix string. Now all characters have been scanned so we must pop the remaining elements from the stack and add it to the Postfix string. At this stage we have only a '-' in the stack. It is popped out and added to the Postfix string. So, after all characters are scanned, this is how the stack and Postfix string will be :

Stack

Postfix String

End result :

• Infix String : a+b*c-d
• Postfix String : abc*+d-

Answer 4

#include<stdio.h>

#include<ctype.h>

#include<string.h>

#define TRUE 1

#define FALSE 0

#define MAX 100

typedef struct stack {

int top;

union array {

char items[MAX][MAX];

int intitems[MAX];

} a;

} s;

void Post_In(void); /* Function Prototypes */

int convertpostfix(char postfix[], char infix[][MAX]);

void Pre_In(void);

void Reduce(void);

int convertprefix(char prefix[], char infix[][MAX]);

void remove_superfluous_parantheses(char infix[], char reducedinfix[]);

void push(s *pt, char operand[]);

void pop(s *pt, char operand[]);

int empty(s *pt);

int isoperand(char symb);

int prcd(char symb);

int popindex(s *pt);

void pushindex(s *pt, int index);

void removeindices(s *pt1, s *pt2);

void formexpression(char op1[], char op2[], char symb, char operand[]);

/***************************** Postfix To Infix ****************************/

void Post_In(void) {

int i, n;

char postfix[MAX], *string, reducedinfix[MAX], infix[MAX][MAX];

for (i = 0; (postfix[i] = getchar()) != '\n'; ++i)

;

postfix[i] = '\0';

n = convertpostfix(postfix, infix);

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

strcat(string, infix[i]);

remove_superfluous_parantheses(string, reducedinfix);

return;

}

int convertpostfix(char postfix[], char infix[][MAX]) {

int k;

char symb, operand[MAX], op1[MAX], op2[MAX];

s opndstack;

opndstack.top = -1;

for (k = 0; (symb = postfix[k]) != '\0'; ++k)

if (isoperand(symb)) {

/* converting symb to a string */

operand[0] = symb;

operand[1] = '\0';

/* pushing the operand into the stack */

push(&opndstack, operand);

} else {

pop(&opndstack, op2);

pop(&opndstack, op1);

formexpression(op1, op2, symb, operand);

/* pushing the infix expression into the stack */

push(&opndstack, operand);

}

/* copying the final infix expression from the stack into the infix array */

for (k = 0; !empty(&opndstack); ++k)

pop(&opndstack, infix[k]);

return (k); /* k is the count of the no of operands in the stack */

}

/****************************** Prefix To Infix *****************************/

void Pre_In(void) {

int i, n;

char prefix[MAX], *string, reducedinfix[MAX], infix[MAX][MAX];

for (i = 0; (prefix[i] = getchar()) != '\n'; ++i)

;

prefix[i] = '\0';

n = convertprefix(prefix, infix);

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

strcat(string, infix[i]);

remove_superfluous_parantheses(string, reducedinfix);

return;

}

int convertprefix(char prefix[], char infix[][MAX]) {

int k, length;

char symb, operand[MAX], op1[MAX], op2[MAX];

s opndstack;

opndstack.top = -1;

for (k = 0; prefix[k] != '\0'; ++k)

;

length = k - 1;

for (k = length; k >= 0; --k)

if (isoperand(symb = prefix[k])) {

/* converting symb to a string */

operand[0] = symb;

operand[1] = '\0';

/* pushing the operand into the stack */

push(&opndstack, operand);

} else {

pop(&opndstack, op1);

pop(&opndstack, op2);

formexpression(op1, op2, symb, operand);

/*pushing the infix expression into the stack */

push(&opndstack, operand);

}

/* copying the final infix expression from the stack into the infix array */

for (k = 0; !empty(&opndstack); ++k)

pop(&opndstack, infix[k]);

return (k);

}

/********************* Removal of Superfluous Parantheses ******************/

void Reduce(void) {

int i;

char infix[MAX], reducedinfix[MAX];

for (i = 0; (infix[i] = getchar()) != '\n'; ++i)

;

infix[i] = '\0';

remove_superfluous_parantheses(infix, reducedinfix);

return;

}

/***************************** Common Functions ****************************/

void remove_superfluous_parantheses(char infix[], char reducedinfix[]) {

/* neededleft and neededright arrays will contain the indices of only the required parantheses */

int i, j, k, lcntr, rcntr, present, hold, neededleft[MAX], neededright[MAX];

int prcdlast, prcdfirst;

char symb, lastoperator, firstoperator;

s leftstack, rightstack;

leftstack.top = rightstack.top = -1;

lcntr = rcntr = 0;

for (i = 0; (symb = infix[i]) != '\0'; ++i)

if (symb -1 ? TRUE : FALSE);

}

int isoperand(char symb) {

return (isalpha(symb) ? TRUE : FALSE);

}

/***************************************************************************/

void main() // main function

{

Post_In();

Pre_In();

Reduce();

}

Answer 5

#include <stdio.h>

#include <stdlib.h>

#define max 20

typedef enum status_code{failure,success}status_code;

typedef struct node_tag

{

char operator;

struct node_tag *next;

}node;

typedef struct queue

{

struct node_tag *front;

struct node_tag *rear;

}queue;

void initialise_queue(queue *qptr)

{

qptr->front=NULL;

qptr->rear=NULL;

}

status_code insert_node(node **lptr,char val)

Answer 6

Write and explain a 'C' function to convert the given infix expression to postfix expressionWrite and explain a 'C' function to convert the given infix expression to postfix expression