[go: up one dir, main page]
Scribd
Upload
23 views4 pages

APAssignment 3

The document describes an algorithm to: 1) Convert an infix expression to a postfix expression by using a stack. Operators are pushed and popped from the stack based on their precedence. 2) Evaluate the postfix expression by using a stack to pop the operands and push the result of operations. 3) The program takes an infix expression and operand values as input from the user and outputs the postfix expression and its evaluation.

Uploaded by

Dharmatej Mallampati
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
23 views4 pages

APAssignment 3

The document describes an algorithm to: 1) Convert an infix expression to a postfix expression by using a stack. Operators are pushed and popped from the stack based on their precedence. 2) Evaluate the postfix expression by using a stack to pop the operands and push the result of operations. 3) The program takes an infix expression and operand values as input from the user and outputs the postfix expression and its evaluation.

Uploaded by

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

Assignment 3

-----------------------------------------------------------------------------------
Write a program where the input is an infix expression kept in a string,
convert it into a postfix expression and evaluate it. The operands'
values are also taken as user input after receiving the string.

Arithmetic expressions can be expressed in the following ways


Infix Expression: In this notation the operator lies between the two
working operands.
Operand_1 Operator Operand_2
Postfix Expression: In this notation the operator lies after the two
working operands. Postfix evaluation is simple and efficient way to
compute arithmetic expressions.
Operand_1 Operand_2 Operator

The infix to postfix conversion is an application of Stacks. Stacks can


be implemented using linked lists and arrays. Here the code is written
by the implementation of stacks using arrays.

ALGORITHM 1:
1) Here the name of the array is exp (refered as stack).
2) Traverse the infix epression from left to right
3) For(I=0;exp[I];++I)
K=exp[I]
4) Compare the character k with the operators and do the
respective function
5) If k = ‘(‘ : push it onto the stack
6) If k = ‘)’ : pop all the operators in the stack untill ‘)’
7) If k = ‘+’ or ‘-’ or ‘*’ or ‘/’ or ‘^’ : check the precedence. If higher
precendence operator is present in the stack then pop it, if not
then push the current operator into the stack.
8) If k = any operand: push it onto the stack

The function for the above algorithm is as follows:

int InToPost(char* exp)


{

int i,j;
for (i = 0,j = -1; exp[i]; ++i)
{
char k = exp[i];

switch (k)
{
case '(': //leftparanthesis
push(k);
break;
case ')': //rightparanthesis

while (!isEmpty() && peek() != '(')


exp[++j] = pop();
if (!isEmpty() && peek() != '(')
return -1;
else
pop();
break;
case '+':
case '-':
case '*': //operators
case '/':
case '^':
while (!isEmpty() && precedence(k) <= precedence(peek()))
exp[++j] = pop();
push(k);
break;
default: //operands
exp[++j] = k;
}
}
while (!isEmpty())
{
if (peek() == '(')
return -1;
exp[++j] = pop();
}

exp[++j] = '\0';
printf("The Postfix Expression is: ");
printf( "%s", exp);
printf("\n");
return 0;
}

ALGORITHM 2:

1. Traverse the infix expression with the values which is given by


the user from left to right.
2. For(I=0;exp[I];++I)
K=exp[I]
3. If k is a digit from 0 to 9: push it into the stack.
4. If k = ‘+’ or ‘-’ or ‘*’ or ‘/’ : pop the previous two elemens of the
stack and do their respective arithmetic operations.
5. Then push the result into the same stack.
6. Continue this till no elements are present in the stack.
7. Then pop the result and print it as the postfix evaluation for the
given infix expression

The function for the above algorithm is as follows:

int calculate(char* exp)


{
int i = 0;
char k;
k = exp[i];
int operand1, operand2, result;

while (k!= '\0')


{
if (k >= '0' && k <= '9') //digits
{
int num = k - '0';
push(num);
}
else if (k=='+'|| k=='-'|| k=='*'|| k=='/'). //operators
{
operand2 = pop();
operand1 = pop();
switch(k)
{
case '+': result = operand1 + operand2;
break;
case '-': result = operand1 - operand2;
break;
case '*': result = operand1 * operand2;
break;
case '/': result = operand1 / operand2;
break;
}
push(result); //result
}
i++;
k = exp[i];
}
result = pop();
return result;
}

You might also like