Write a class that converts an infix expression to a postfix expression using th
ID: 3756533 • Letter: W
Question
Write a class that converts an infix expression to a postfix expression using the algorithm posted below. It also requires a default constructor and and a constructor that takes an object of type StackInterface as its only parameter. If the default constructor is used, then the private member (of type StackInterface) should be initialized to a new LinkedStack If the other constructor is used then you should set your internal StackInterface reference variable to point to the object passed in by parameter _________________________________________________________________________________ public class InfixToPostfixConverter implements ExpressionConverterInterface { //default constructor //constructor that takes an object of type StackInterface as its only parameter //***************************************************************************** public convertToPostfix(int infix){ operatorStack = //a new empty stack postfix = //a new empty string while (//infix has characters left to parse){ nextCharacter = //next nonblank character of infix switch(nextCharacter) { case variable //Append nextCharacter to postfix break case '^': operatorStack.push(nextCharacter) break; case '+': case '-': case '*': case '/': while (!operatorStack.isEmpty()) //and //precedence of nextCharacter <= precedence of operatorStack.peek() { //append operatorStack.peek() to postfix operatorStack.pop(); } operatorStack.push(nextCharacter) break; case '(': operatorStack.push(nextCharacter) case ')': topOperator = operatorStack.pop(); while (topOperator != '(') { //Append topOperator to postfix topOperator = operatorStack.pop(); } break; default: break //Ignore unexpected characters } } while(!operatorStack.isEmpty()){ topOperator = operatorStack.pop(); //Append topOperator to postfix } return postfix; //***************************************************************************** public evaluatePostfix(postfix) //evaluates a postfix expression valueStack = //a new empty stack while(//postfix has characters to parse) { nextCharacter = //next nonblank character of postfix switch (nextCharacter) { case variable: valueStack.push(//value of the variable nextCharacter) break; case '+' : case '-' : case '*' : case '/' : case '^' : operandTwo = valueStack.pop(); operandOne = valueStack.pop(); result = //the result of the operation in nextCharacter and its operands //operandOne and operandTwo valueStack.push(result) break; default: break //ignore unexpected } } //***************************************************************************** public evaluateInfix(infix) //evaluates an infix expression operatorStack = //a new empty stack valueStack = //a new empty stack while(//infix has characters left to process) { nextCharacter = //next nonblank character of infix switch (nextCharacter) { case //variable: valueStack.push(//value of the variable nextCharacter) break; case '^' : operatorStack.push(nextCharacter) break; case '+' : case '-' : case '*' : case '/' : while (!operatorStack.isEmpty()) //and //precedence of nextCharacter <= precedence of operatorStack.peek()) { //Execute operator at top of operatorStack topOperator = operatorStack.pop() operandTwo = valueStack.pop() operandOne = valueStack.pop() result = //the result of the operation in topOperator and its operand //operandOne and operandTwo valueStack.push(result) } operatorStack.push(nextCharacter) break case'(': operatorStack.push(nextCharacter) break case '(': operatorStack.push(nextCharacter) break case ')': //stack is not empty if infix expression is valid topOperator = operatorStack.pop() while (topOperator != '(') { operandTwo = valueStack.pop() operandOne = valueStack.pop() result = //the result of the operation in topOperator and its operand //operandOne and operandTwo valueStack.push(result) topOperator = operatorStack.pop() } break } default: break while(!operatorStack.isEmpty()) { topOperator = operatorStack.pop() operandTwo = valueStack.pop() operandOne = valueStack.pop() result = //the result of the operation in topOperator and its operand //operandOne and operandTwo valueStack.push(result) } return valueStack.peek() } } }
Explanation / Answer
Infix expression:The articulation of the frame an operation b. At the point when an administrator is in the middle of each combine of operands.
Postfix expression:The articulation of the frame a b operation. At the point when an administrator is taken after for each match of operands.
Why postfix portrayal of the articulation?
The compiler filters the articulation either from left to right or from appropriate to left.
Consider the underneath articulation: an op1 b op2 c op3 d
On the off chance that op1 = +, op2 = *, op3 = +
The compiler first outputs the articulation to assess the articulation b * c, on the other hand check the articulation to add a to it. The outcome is then added to d after another output.
The continued examining makes it extremely in-proficient. It is smarter to change over the articulation to postfix(or prefix) frame before assessment.
The relating articulation in postfix frame is: abc*+d+. The postfix articulations can be assessed effectively utilizing a stack. We will cover postfix articulation assessment in a different post.
Calculation
1. Sweep the infix articulation from left to right.
2. On the off chance that the examined character is an operand, yield it.
3. Else,
… ..3.1 If the priority of the checked administrator is more noteworthy than the priority of the administrator in the stack(or the stack is vacant), push it.
… ..3.2 Else, Pop the administrator from the stack until the priority of the checked administrator is less-equivalent to the priority of the administrator dwelling on the highest point of the stack. Push the filtered administrator to the stack.
4. In the event that the checked character is a '(', push it to the stack.
5. In the event that the filtered character is a ')', pop and yield from the stack until a '(' is experienced.
6. Rehash stages 2-6 until infix articulation is checked.
7. Pop and yield from the stack until the point when it isn't vacant.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct Stackk
{
int topp;
unsigned capacityy;
int* arry;
};
struct Stackk* createStack( unsigned capacityy )
{
struct Stackk* stck = (struct Stackk*) malloc(sizeof(struct Stackk));
if (!stck)
return NULL;
stck->topp = -1;
stck->capacityy = capacityy;
stck->arry = (int*) malloc(stck->capacityy * sizeof(int));
if (!stck->arry)
return NULL;
return stck;
}
int isEmpty(struct Stackk* stck)
{
return stck->topp == -1 ;
}
char peek(struct Stackk* stck)
{
return stck->arry[stck->topp];
}
char pop(struct Stackk* stck)
{
if (!isEmpty(stck))
return stck->arry[stck->topp--] ;
return '$';
}
void push(struct Stackk* stck, char op)
{
stck->arry[++stck->topp] = op;
}
int isOperand(char chr)
{
return (chr >= 'a' && chr <= 'z') || (chr >= 'A' && chr <= 'Z');
}
int Prec(char chr)
{
switch (chr)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
int infixToPostfix(char* expr)
{
int x, k;
struct Stackk* stck = createStack(strlen(expr));
if(!stck)
return -1 ;
for (x = 0, k = -1; expr[x]; ++x)
{
if (isOperand(expr[x]))
expr[++k] = expr[x];
else if (expr[x] == '(')
push(stck, expr[x]);
else if (expr[x] == ')')
{
while (!isEmpty(stck) && peek(stck) != '(')
expr[++k] = pop(stck);
if (!isEmpty(stck) && peek(stck) != '(')
return -1;
else
pop(stck);
}
else
{
while (!isEmpty(stck) && Prec(expr[x]) <= Prec(peek(stck)))
expr[++k] = pop(stck);
push(stck, expr[x]);
}
}
while (!isEmpty(stck))
expr[++k] = pop(stck );
expr[++k] = '';
printf( "%sn", expr );
}
int main()
{
char expr[] = "a+b*(c^d-e)^(f+g*h)-x";
infixToPostfix(expr);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.