Postfix notation is an unambiguous way of writing an arithmetic expression witho
ID: 3793982 • Letter: P
Question
Postfix notation is an unambiguous way of writing an arithmetic expression without parentheses It is defined so that if "(exp1)op(exp2)" is a normal fully parenthesized expression whose operation is op. the postfix version of this it "pexp1pexp2 op", where pexp1 is the postfix version of exp2 and pexp1 is the postfix version of exp2. The postfix version of a single number or variable is just that number or variable. So. for example, the postfix version of "((5+2) middot (8-3))/4" is "5 2 + 8 3 - * 4/". Use pseudocode to describe a nonrecursive way of evaluating an expression in postfix notation by using a stack (Your method should return a Boolean value to indicate whether the expression is valid or not.) : provide java code for your method and test examples.Explanation / Answer
HI, Please find my algorithm and Java code to evaluate POSTFIX expression.
Please let me know in case of any issue.
ALGORITHM:
Following is algorithm for evaluation postfix expressions.
1) Create a stack to store operands (or values).
2) Scan the given expression and do following for every scanned element.
.a) If the element is a number, push it into the stack
.b) If the element is a operator, pop operands for the operator from stack. Evaluate the operator and push
the result back to the stack
3) When the expression is ended, the number in the stack is the final answer
Example:
Let the given expression be “2 3 1 * + 9 -“. We scan all elements one by one.
1) Scan ‘2’, it’s a number, so push it to stack. Stack contains ‘2’
2) Scan ‘3’, again a number, push it to stack, stack now contains ‘2 3 (from bottom to top)
3) Scan ‘1’, again a number, push it to stack, stack now contains ‘2 3 1
4) Scan ‘*’, it’s an operator, pop two operands from stack, apply the * operator on operands, we get 3*1 which results in 3. We push the result ‘3’ to stack. Stack now becomes ‘2 3.
5) Scan ‘+’, it’s an operator, pop two operands from stack, apply the + operator on operands, we get 3 + 2 which results in 5. We push the result ‘5’ to stack. Stack now becomes ‘5’.
6) Scan ‘9’, it’s a number, we push it to the stack. Stack now becomes ‘5 9.
7) Scan ‘-‘, it’s an operator, pop two operands from stack, apply the – operator on operands, we get 5 – 9 which results in -4. We push the result ‘-4 to stack. Stack now becomes ‘-4.
8) There are no more elements to scan, we return the top element from stack (which is the only element left in stack).
JAVA CODE:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class PostfixEvaluator {
public static int evaluate(char[] postfix) {
int n, r = 0;
n = postfix.length;
Stack<Integer> a = new Stack<Integer>();
for (int i = 0; i < n; i++) {
char ch = postfix[i];
if (ch >= '0' && ch <= '9')
a.push(ch - '0');
else if (ch == ' ')
continue;
else {
int x = a.pop();
int y = a.pop();
switch (ch) {
case '+':
r = x + y;
break;
case '-':
r = y - x;
break;
case '*':
r = x * y;
break;
case '/':
r = y / x;
break;
default:
r = 0;
}
a.push(r);
}
}
r = a.pop();
return (r);
}
// main method
public static void main(String[] args)throws IOException
{
String postfix;
while(true)
{
System.out.println("Enter the postfix expresion(of enter Q/q to stop)");
postfix=getString();
if(postfix.equalsIgnoreCase("q"))
break;
System.out.println("Postfix Expression:- "+postfix);
System.out.println("Evaluated value of postfix: "+evaluate(postfix.toCharArray()));
}
}
public static String getString()throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
}
/*
Sample run:
Enter the postfix expresion(of enter Q/q to stop)
34+
Postfix Expression:- 34+
Evaluated value of postfix: 7
Enter the postfix expresion(of enter Q/q to stop)
456/+
Postfix Expression:- 456/+
Evaluated value of postfix: 4
Enter the postfix expresion(of enter Q/q to stop)
2 3 1 * + 9 -
Postfix Expression:- 2 3 1 * + 9 -
Evaluated value of postfix: -4
Enter the postfix expresion(of enter Q/q to stop)
q
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.