Modify Listing 20.12, EvaluateExpression.java, to add
operators ^ for exponent and % for remainder. 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: 349 % 23 ^ 2 + 4 ^ 4 %* 5

349 % 23 ^ 2 + 4 ^ 4 % 5 = 350

Here is the Listing 20.12 to modify:

import java.util.Stack;

public class EvaluateExpression {

  public static void main(String[] args) {

    // Check number of arguments passed

    if (args.length != 1) {

      System.out.println(

        "Usage: java EvaluateExpression "expression"");

      System.exit(1);

    }

    try {

      System.out.println(evaluateExpression(args[0]));

    }

    catch (Exception ex) {

      System.out.println("Wrong expression: " + args[0]);

    }

  }

  /** Evaluate an expression */

  public static int evaluateExpression(String expression) {

    // Create operandStack to store operands

    Stack operandStack = new Stack<>();

 

    // Create operatorStack to store operators

    Stack 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 operandStack, Stack 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;

  }

}