Java (Evaluate expression) Modify Listing 20.9 EvaluateExpression.java to add op
ID: 3668185 • Letter: J
Question
Java
(Evaluate expression) Modify Listing 20.9 EvaluateExpression.java to add
operators ^ for exponent and % for modulus. For example, 3 ^ 2 is 9 and 3 % 2
is 1. The ^ operator has the highest precedence and the % operator has the same
precedence as the * and / operators. Your program should prompt the user to
enter an expression.
Here is a sample run of the program:
Enter an expression: (5 * 2 ^ 3 + 2 * 3 % 2) * 4
(5 * 2 ^ 3 + 2 * 3 % 2) * 4 = 160
Listing 20.9
import java.util.Stack;
import java.util.Scanner;
public class Beginning {
public static void main(String[] args) {
// Check number of arguments passed
String[] go = {"(5+32)*4"};
if (go.length != 1) {
System.out.println(
"Usage: java EvaluateExpression "expression"");
System.exit(1);
}
try {
System.out.println(evaluateExpression(go[0]));
}
catch (Exception ex) {
System.out.println("Wrong expression: " + go[0]);
}
}
/** Evaluate an expression */
public static int evaluateExpression(String expression) {
// Create operandStack to store operands
Stack<Integer> operandStack = new Stack<>();
// Create operatorStack to store operators
Stack<Character> operatorStack = new Stack<>();
// Insert blanks around (, ), +, -, /, and *
expression = insertBlanks(expression);
// Extract operands and operators
String[] tokens = expression.split(" ");
// Phase 1: Scan tokens
for (String token: tokens) {
if (token.length() == 0) // Blank space
continue; // Back to the while loop to extract the next token
else if (token.charAt(0) == '+' || token.charAt(0) == '-') {
// Process all +, -, *, / in the top of the operator stack
while (!operatorStack.isEmpty() &&
(operatorStack.peek() == '+' ||
operatorStack.peek() == '-' ||
operatorStack.peek() == '*' ||
operatorStack.peek() == '/')) {
processAnOperator(operandStack, operatorStack);
}
// Push the + or - operator into the operator stack
operatorStack.push(token.charAt(0));
}
else if (token.charAt(0) == '*' || token.charAt(0) == '/') {
// Process all *, / in the top of the operator stack
while (!operatorStack.isEmpty() &&
(operatorStack.peek() == '*' ||
operatorStack.peek() == '/')) {
processAnOperator(operandStack, operatorStack);
}
// Push the * or / operator into the operator stack
operatorStack.push(token.charAt(0));
}
else if (token.trim().charAt(0) == '(') {
operatorStack.push('('); // Push '(' to stack
}
else if (token.trim().charAt(0) == ')') {
// Process all the operators in the stack until seeing '('
while (operatorStack.peek() != '(') {
processAnOperator(operandStack, operatorStack);
}
operatorStack.pop(); // Pop the '(' symbol from the stack
}
else { // An operand scanned
// Push an operand to the stack
operandStack.push(new Integer(token));
}
}
// Phase 2: Process all the remaining operators in the stack
while (!operatorStack.isEmpty()) {
processAnOperator(operandStack, operatorStack);
}
// Return the result
return operandStack.pop();
}
/** Process one operator: Take an operator from operatorStack and
* apply it on the operands in the operandStack */
public static void processAnOperator(
Stack<Integer> operandStack, Stack<Character> operatorStack) {
char op = operatorStack.pop();
int op1 = operandStack.pop();
int op2 = operandStack.pop();
if (op == '+')
operandStack.push(op2 + op1);
else if (op == '-')
operandStack.push(op2 - op1);
else if (op == '*')
operandStack.push(op2 * op1);
else if (op == '/')
operandStack.push(op2 / op1);
}
public static String insertBlanks(String s) {
String result = "";
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(' || s.charAt(i) == ')' ||
s.charAt(i) == '+' || s.charAt(i) == '-' ||
s.charAt(i) == '*' || s.charAt(i) == '/')
result += " " + s.charAt(i) + " ";
else
result += s.charAt(i);
}
return result;
}
}
Explanation / Answer
package com.java2novice.ds.stack;
import java.util.StringTokenizer;
public class InfixFullParantEx {
public static String evaluateInfix(String exps){
/**remove if any spaces from the expression**/
exps = exps.replaceAll("\s+", "");
/**we assume that the expression is in valid format**/
MyGenericsStack<String> stack = new MyGenericsStack<String>(exps.length());
/**break the expression into tokens**/
StringTokenizer tokens = new StringTokenizer(exps, "{}()*/+-", true);
while(tokens.hasMoreTokens()){
String tkn = tokens.nextToken();
/**read each token and take action**/
if(tkn.equals("(")
|| tkn.equals("{")
|| tkn.matches("[0-9]+")
|| tkn.equals("*")
|| tkn.equals("/")
|| tkn.equals("+")
|| tkn.equals("-")){
/**push token to the stack**/
stack.push(tkn);
} else if(tkn.equals("}") || tkn.equals(")")){
try {
int op2 = Integer.parseInt(stack.pop());
String oprnd = stack.pop();
int op1 = Integer.parseInt(stack.pop());
/**Below pop removes either } or ) from stack**/
if(!stack.isStackEmpty()){
stack.pop();
}
int result = 0;
if(oprnd.equals("*")){
result = op1*op2;
} else if(oprnd.equals("/")){
result = op1/op2;
} else if(oprnd.equals("+")){
result = op1+op2;
} else if(oprnd.equals("-")){
result = op1-op2;
}
/**push the result to the stack**/
stack.push(result+"");
} catch (Exception e) {
e.printStackTrace();
break;
}
}
}
String finalResult = "";
try {
finalResult = stack.pop();
} catch (Exception e) {
e.printStackTrace();
}
return finalResult;
}
public static void main(String a[]){
String expr = "((2*5)+(6/2))";
System.out.println("Expression: "+expr);
System.out.println("Final Result: "+evaluateInfix(expr));
expr = "(((2 * 5) - (1 * 2)) / (11 - 9))";
System.out.println("Expression: "+expr);
System.out.println("Final Result: "+evaluateInfix(expr));
}
}
/**
* Stack implementation
*/
public class MyGenericsStack<T extends Object> {
private int stackSize;
private T[] stackArr;
private int top;
/**
* constructor to create stack with size
* @param size
*/
@SuppressWarnings("unchecked")
public MyGenericsStack(int size) {
this.stackSize = size;
this.stackArr = (T[]) new Object[stackSize];
this.top = -1;
}
/**
* This method adds new entry to the top
* of the stack
* @param entry
* @throws Exception
*/
public void push(T entry){
if(this.isStackFull()){
System.out.println(("Stack is full. Increasing the capacity."));
this.increaseStackCapacity();
}
System.out.println("Adding: "+entry);
this.stackArr[++top] = entry;
}
/**
* This method removes an entry from the
* top of the stack.
* @return
* @throws Exception
*/
public T pop() throws Exception {
if(this.isStackEmpty()){
throw new Exception("Stack is empty. Can not remove element.");
}
T entry = this.stackArr[top--];
System.out.println("Removed entry: "+entry);
return entry;
}
/**
* This method returns top of the stack
* without removing it.
* @return
*/
public T peek() {
return stackArr[top];
}
private void increaseStackCapacity(){
@SuppressWarnings("unchecked")
T[] newStack = (T[]) new Object[this.stackSize*2];
for(int i=0;i<stackSize;i++){
newStack[i] = this.stackArr[i];
}
this.stackArr = newStack;
this.stackSize = this.stackSize*2;
}
/**
* This method returns true if the stack is
* empty
* @return
*/
public boolean isStackEmpty() {
return (top == -1);
}
/**
* This method returns true if the stack is full
* @return
*/
public boolean isStackFull() {
return (top == stackSize - 1);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.