What is polish expression and how to solve it?


#1

Please explain me how to do question 2.11


#2

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

  1. Initialize stack
  2. 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
  3. 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.


#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+bc, the expression part bc 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.


#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;
}