The concept of stack is extremely important in computer science and is used in a wide variety of problems. This assignment requires you to write a program that can be used to evaluate ordinary arithmetic expressions that contains any of the five arithmetic operators (+, -, *, /, %). This exercise requires three distinct steps, namely:- 1. Verify that the infix arithmetic expression (the original expression), that may contain regular parentheses, is properly formed as far as parentheses are concerned. 2. If the parenthesized expression is properly formed, convert the expression from an infix expression to its equivalent postfix expression, called Reverse Polish Notation (RPN) named after the Polish Mathematician J. Lukasiewics. 3. Evaluate the postfix expression, and print the result. Step 1 - Verify that the expression Given an arithmetic expression, called an infixed expression, to verify that it is properly formed as far as parentheses are concerned, do the following: 1 Create an empty stack to hold left parenthesis ONLY. 2 Scanned the arithmetic expression from left to right, one character at a time. 3 While there are more characters in the arithmetic expression { If the character is a left parenthesis (, push it on to the stack. However if the character is a right parenthesis, ), visit the stack and pop the top element from off the stack. } If the stack contains any element at the end of reading the arithmetic expression, then the expression was not properly formed. Use the following code below as your Main Test class:

class RPN

{

public static void main(String[] arg)

{

String s[] = {"5 + ) * ( 2",

" 2 + ( - 3 * 5 ) ",

"(( 2 + 3 ) * 5 ) * 8 ",

"5 * 10 + ( 15 - 20 ) ) - 25",

" 5 + ( 5 * 10 + ( 15 - 20 ) - 25 ) * 9"

};

for (int i = 0; i < s.length; i++)

{

Arithmetic a = new Arithmetic(s[i]);

if (a.isBalance())

{

System.out.println("Expression " + s[i] + " is balanced ");

a.postfixExpression();

System.out.println("The post fixed expression is " + a.getPostfix());

a.evaluateRPN();

// Supply the necessary codes to determine the validity of your answers

}

else

System.out.println("Expression is not balanced ");

}

}

}

-------------------------------------------------------------

import java.util.Stack;

import java.util.EmptyStackException;

import java.util.Scanner;

class Arithmetic

{

Stack stk;

String expression,

postfix;

int length;

Arithmetic(String s)

{

expression = s;

postfix ="";

length = expression.length();

stk = new Stack();

}

// Validate the expression - make sure parentheses are balanced

boolean isBalance()

{

// Already defined

}

// Convert expression to postfix notation

void postfixExpression()

{

stk.clear(); // Re-using the stack object

Scanner scan = new Scanner(expression);

char current;

// The algorithm for doing the conversion.... Follow the bullets

while (scan.hasNext())

{

String token = scan.next();

if (isNumber(token)) // Bullet # 1

postfix = postfix + token + " ";

else

{

current = token.charAt(0);

if (isParentheses(current)) // Bullet # 2 begins

{

if(stk.empty() || current == Constants.LEFT_NORMAL)

{

// push this element on the stack;

}

else if (current == Constants.RIGHT_NORMAL)

{

try

{

/* Some details ... whatever is popped from the

* stack is an object, hence you must cast this

* object to its proper type, then extract its

* primitive data (type) value.

*/

Character ch = (Character)stk.pop();

char top = ch.charValue();

while (top != Constants.LEFT_NORMAL)

{

/* Append token popped onto the output string

* Place at least one blank space between

* each token

*/

}

}

catch(EmptyStackException e)

{

}

}

}// Bullet # 2 ends

else if (isOperator(current))// Bullet # 3 begins

{

if(stk.empty())

stk.push(new Character(current));

else

{

try

{

// Remember the method peek simply looks at the top

// element on the stack, but does not remove it.

char top = (Character)stk.peek();

boolean higher = hasHigherPrecedence(top, current);

while(top != Constants.LEFT_NORMAL && higher)

{

postfix = postfix + stk.pop() + " ";

top = (Character)stk.peek();

}

stk.push(new Character(current));

}

catch(EmptyStackException e)

{

stk.push(new Character(current));

}

}

}// Bullet # 3 ends

}

} // Outer loop ends

try

{

while(!stk.empty()) // Bullet # 4

; // complete this

}

catch(EmptyStackException e)

{

}

}

boolean isNumber(String str)

{

//define this method

}

boolean isParentheses(char current)

{

// define this method;

}

boolean isOperator(char ch)

{

// define this method

}

boolean hasHigherPrecedence(char top, char current)

{

// define this method

}

String getPostfix()

{

// define method

}

--------------------------------------------------------------------------------

import java.util.EmptyStackException;

import java.util.Stack;

public class Arithmetic

{

private Stack