Let ‘operandstk’ be an empty stack then the algorithm to evaluate prefix
expression is:
1.
Start
2.
Input a prefix expression in the ‘prefix’ string.
3.
for each last character ‘ch’ of ‘prefix’
string
if(‘ch’ is an
operand)
push ‘ch’ in ‘operandstk’
else
{
opnd2= pop an operand from ‘operandstk’
opnd1= pop an operand from ‘operandstk’
value= result of applying ‘ch’ in ‘opnd2’
and ‘opnd1’
push ‘value’ to ‘operandstk’
}
4.
pop the top element of the stack ‘operandstk’ which is the required
result.
5.
Exit
TRACING THE ALGORITHM:
prefix string: + + 2 * 3 2 / 10 2
|
ch
|
opnd1
|
opnd2
|
value
|
operandstk
|
|
2
|
|
|
|
2
|
|
10
|
|
|
|
2, 10
|
|
/
|
2
|
10
|
5
|
5
|
|
2
|
2
|
10
|
5
|
5,2
|
|
3
|
2
|
10
|
5
|
5, 2, 3
|
|
*
|
2
|
3
|
6
|
5,6
|
|
2
|
2
|
3
|
6
|
5, 6, 2
|
|
+
|
6
|
2
|
8
|
5, 8
|
|
+
|
5
|
8
|
13
|
13
|
∴The result of the prefix expression: + + 2 * 3 2 / 10 2 is
pop(operandstk)= 13.
plz upload c++ code of above algorithm...
ReplyDeleteJava Code :
ReplyDeletepublic static int evaluatePrefix(String exp)
{
String[] tokens = exp.split(" ");
Stack operand = new Stack();
for(int i=tokens.length-1;i>=0;i--)
{
if(tokens[i].compareTo("+") != 0 && tokens[i].compareTo("-") !=0 && tokens[i].compareTo("*") !=0 && tokens[i].compareTo("/") != 0) //not an operator
{
operand.push(Integer.parseInt(tokens[i]));
}
else
{
int op1 = operand.pop();
int op2 = operand.pop();
int result;
switch(tokens[i])
{
case "+":result = op1+op2;
break;
case "-":result = op1-op2;
break;
case "*":result = op1*op2;
break;
case "/":result = op1/op2;
break;
default: result=0;
}
operand.push(result);
}
}
return operand.pop();
}
best site.its very easy to understand the articles.
ReplyDeleteFull Stack Training in Chennai | Certification | Online Training Course | Full Stack Training in Bangalore | Certification | Online Training Course | Full Stack Training in Hyderabad | Certification | Online Training Course | Full Stack Training in Pune | Certification | Online Training Course | Full Stack Training | Certification | Full Stack Online Training Course