Write a program to evaluate an arithmetic expression written in postfixed notati
ID: 3670400 • Letter: W
Question
Write a program to evaluate an arithmetic expression written in postfixed notation. The arithmetic expression will be input as a String (by the user) and will contain only integer operands. Use the following code sequences to parse (i.e., remove) the integers and the operators from the input string, mathExpression:
import java.util;
String thisToken;
StringTokenizer tokens = new StringTokenizer(mathExpression);
while(tokens.hasMoreTokens())
{ thisToken = tokens.nextToken();
//processing for thisToken goes here
}
Explanation / Answer
import java.util.*;
public class PostFix
{
public static int evaluate(String expression)
{
char[] tokens = expression.toCharArray();
// Stack for numbers: 'values'
Stack<Integer> values =new Stack<Integer>();
// Stack for Operators: 'ops'
Stack<Character> ops =new Stack<Character>();
for (int i =0; i < tokens.length; i++)
{
// Current token is a whitespace, skip it
if (tokens[i] ==' ')
continue;
// Current token is a number, push it to stack for numbers
if (tokens[i] >='0' && tokens[i] <='9')
{
StringBuffer sbuf =new StringBuffer();
// There may be more than one digits in number
while (i < tokens.length && tokens[i] >='0' && tokens[i] <='9')
sbuf.append(tokens[i++]);
values.push(Integer.parseInt(sbuf.toString()));
}
// Current token is an opening brace, push it to 'ops'
else if (tokens[i] =='(')
ops.push(tokens[i]);
// Closing brace encountered, solve entire brace
else if (tokens[i] ==')')
{
while (ops.peek() !='(')
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
ops.pop();
}
// Current token is an operator.
else if (tokens[i] =='+' || tokens[i] =='-' ||
tokens[i] =='*' || tokens[i] =='/')
{
// While top of 'ops' has same or greater precedence to current
// token, which is an operator. Apply operator on top of 'ops'
// to top two elements in values stack
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
// Entire expression has been parsed at this point, apply remaining
// ops to remaining values
while (!ops.empty())
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Top of 'values' contains result, return it
return values.pop();
}
// Returns true if 'op2' has higher or same precedence as 'op1',
// otherwise returns false.
public static boolean hasPrecedence(char op1,char op2)
{
if (op2 =='(' || op2 ==')')
return false;
if ((op1 =='*' || op1 =='/') && (op2 =='+' || op2 =='-'))
return false;
else
return true;
}
// A utility method to apply an operator 'op' on operands 'a'
// and 'b'. Return the result.
public static int applyOp(char op,int b,int a)
{
switch (op)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b ==0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return a / b;
}
return 0;
}
// Driver method to test above methods
public static void main(String[] args)
{
System.out.println(EvaluateString.evaluate("10 + 2 * 6"));
System.out.println(EvaluateString.evaluate("100 * 2 + 12"));
System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 )"));
System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 ) / 14"));
}
}
Output:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.