Please explain me how to do question 2.11

# What is polish expression and how to solve it?

**Diksha_Verma**#1

**Prefix Polish** Prefix expression is where operator is before both operand like + 4 5

To evaluate this kind of expression, we can use the stack. Algorithm is

- Initialize stack
- for each element in expression

a. if current element is a operator(+ or *), insert to stack

b. else it will be a number. If top of stack is a operator, insert this number to stack

c. else top of stack will be a number. pop it(say it b). now pop again from stack, it will be a operator. Use it and evaluate the the b and the element.(for +, do b + element, or for * do b * element). Now use this evaluated value as element and go to step 2.a - return top of stack (stack size will be 1).

**Postfix** For postfix, just reverse the expression and and apply the prefix algorithm, that will also work.

**the_rishabh**#3

Before going through algorithm portion

first lets understand about what is polish expression and what is its necessity.

Polish expression refers to notation in which operator symbol is placed before or after its operands in contract to its usual form where operator is placed between operands .

A general expression is high level language , but as we know computer only understands binary language it assume that an arithmetic operation can take place in two operands only as A+B,C*D etc.

But in our usual form of arithmetic expression may consists of more than two operands and one operator as (A+B)*C with the help stack we convert these expression into polish expression i,e. two operand and one operator.

An arithmetic expression can be written in three different but equivalent notations, i.e., without changing the essence or output of an expression.

1.Infix Notation

2Β· Prefix (Polish) Notation

3Β· Postfix (Reverse-Polish) Notation

1.Infix Notation

We write expression in infix notation, e.g. a-b+c, where operators are used in-between operands. It is easy for us humans to read, write and speak in infix notation but the same does not go well with computing devices. An algorithm to process infix notation could be difficult

costly in terms of time and space consumption.

2Β· Prefix (Polish) Notation

In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands.

For example, +ab. This is equivalent to its infix notation a+b. Prefix notation is also known as Polish Notation.

3Β· Postfix (Reverse-Polish) Notation

This notation style is known as Reversed Polish Notation. In this notation style, the operator is postfixed to the operands i.e., the operator is written after the operands.

For example, ab+. This is equivalent to its infix notation a+b.

To parse any arithmetic expression, we need to take care of operator precedence and associativity also.

Operator Precedence Associativity

1 Exponentiation ^ Highest Right Associative

2 Multiplication ( * ) & Division ( / ) Second Highest Left Associative

3 Addition ( + ) & Subtraction ( β ) Lowest Left Associative

In a+b*c, the expression part b*c will be evaluated first, with multiplication as precedence over addition. we have to use parenthesis for a+b to be evaluated first, like (a+b)*c.

Postfix Evaluation Algorithm β

Step 1 β scan the expression from left to right

Step 2 β if it is an operand push it to stack

Step 3 β if it is an operator pull operand from stack and perform operation

Step 4 β store the output of step 3, back to stack

Step 5 β scan the expression until all operands are consumed

Step 6 β pop the stack and perform operation .

For infix to prefix algorithm conversion

Step 1 β scan the expression from right to left.

Other step will be same as postfix algorithm.

**Neha_Goyal**#4

by using algorithium :

firstly make the precedence order of β+β and β*β giving the highest precedence to '*β then β+β and return int;

then input the expression in the form of string

by using this algo:

#include

using namespace std;

char stack[100];

int top=-1;

void push(char val)

{

top=top+1;

stack[top]=val;

}

int prec(char val)

{

if(val==β*β || val ==β/β)
return 5;
else if(val==β+β || val ==β-β)
return 3;
return 0;
}
char peakvalue()
{
return stack[top];
}
char pop()
{
if(top==-1)
{
cout<<βlist is emptyβ;
return 0;
}
return stack[topβ];
}
int main()
{
char t;
int i;
string infix;
string postfix="";
cin>>infix;
infix=infix+β)β;
push(β(β);
for(i=0;infix[i]!=β\0β;i++)
{
t=infix[i];
if(t==β(β)
{
push(t);
}
else if(t==β+β||t==β-β ||t==β*β||t==β/β)

{

while(prec(peakvalue())>=prec(t))

{

postfix=postfix+pop();

}

push(t);

}

else if(t==β)β)

{

while(peakvalue()!=β(β)

{

postfix=postfix+pop();

}

pop();

}

else

postfix=postfix+t;

}

cout<<postfix;

}