Question

This project is designed to practice with OOP, stack data structure, its applications, and C++/Java programming language. You will write a program that reads an infix expression, converts it to a postfix expression, evaluates the postfix expression, and prints out the answer. You must define and implement your own Stack class and a Calculator class. Your Stack class supports standard basic stack operations and you can implement it with an array or a linked list. You should create a class template Stack in C++ or generic class Stack in Java, but an integer stack would work as well since a character is just a subset of integer. Your Calculator class stores an infix expression and it provides the public operations below. Feel free to add additional private operations and data. The Calculator class should use a character stack to convert infix expression to postfix expression (storing operators) and then uses an integer stack to evaluate the postfix expression (storing operands). Public operations in Calculator class: • A constructor that receives a valid expression as string like "5 + 2^3" postfix () - returns the postfix expression eval() - returns the result of the expression setExpr () - receives the infix expression as string and store it getExpr () - returns the infix expression as string Your application (main) should perform the following: • Ask the user to input an infix expression. Examples of an infix expressions might be (you may assume that expressions are valid and tokens are always separated by one space): 177 ( 2 + 3) - 13 5 * 2 * 3 2 A 3 A 2 Create and use a Calculator object to perform conversion and evaluation Obtain and print out the postfix expression (examples above) 17 2 3+ / 13 - 5 2 3 * 2 3 2 A Obtain and print out the answer of the evaluation (examples above) -10 40 512

Answer 1

package DS;

import java.util.*;

import java.util.Stack;

  

// Defines a class InfixToPostfixEvaluate

public class InfixToPostfixEvaluate

{

// Method to evaluate expression

public int evaluateExpression(String stringExpression)

{

// Creates a Stack of type integer

Stack<Integer> numbers = new Stack<>();

// Creates a Stack for operators

Stack<Character> operations = new Stack<>();

  

// Loops till end of the expression

for(int counter = 0; counter <

stringExpression.length(); counter++)

{

// Extracts the current character

char currentCharacter =

stringExpression.charAt(counter);

  

// Check if the current character is a number

if(Character.isDigit(currentCharacter))

{

// To stores the number form of the character

int num = 0;

  

// Loops for greater than one digit number

while (Character.isDigit(currentCharacter))

{

// Converts current character to integer

// by subtracting '0' from it

num = num * 10 + (currentCharacter - '0');

  

// Increase the counter by one

counter++;

  

// Checks if counter value is less than

// expression length

if(counter < stringExpression.length())

// Extracts the character at

// counter index position

currentCharacter =

stringExpression.charAt(counter);

// Otherwise come out of the loop

else

break;

}// End of while loop

  

// Decrease the counter by one

counter--;

  

// Push the number to stack

numbers.push(num);

}// End of if condition

  

// Otherwise checks if the current character is

// Opening parenthesis

else if(currentCharacter == '(')

{

// Push the character to stack

operations.push(currentCharacter);

}// End of else if condition   

  

// Otherwise checks if the current character is

// closing parenthesis

else if(currentCharacter == ')')

{

// Extracts data from stack till

// opening parenthesis

while(operations.peek()!='(')

{

// Calls the method to perform

// calculation

int result = performOperation(numbers,

operations);

// Push the current result to stack

numbers.push(result);

}// End of while loop

  

// Pops out the stack top element

operations.pop();

}// End of else if condition

  

// Otherwise checks if the current character is

// operator

else if(checkForOperator(currentCharacter))

{

// Loops till stack is not empty

// Checks the precedence of operators

// in the stack till highest precedence

while(!operations.isEmpty() &&

operatorPrecedence(currentCharacter)

< operatorPrecedence(

operations.peek()))

{

// Calls the method to perform

// calculation

int result = performOperation(numbers,

operations);

// Pushes the current result to stack

numbers.push(result);

}// End of while loop

  

// Pushes the current operator to stack

operations.push(currentCharacter);

}// End of else if condition

}// End of for loop

  

// Loops till stack is not empty

// for rest of the expression

while(!operations.isEmpty())

{

// Calls the method to perform

// calculation

int result = performOperation(numbers,

operations);

// Pushes the current result to stack

numbers.push(result);

}// End of while loop

// Returns the result by pop out the

// top element from stack

return numbers.pop();

}// End of method

// Method to return operator precedence

static int operatorPrecedence(char currentOperator)

{

// Checks the current operator

// and returns the operator precedence

switch (currentOperator)

{

case '+':

case '-':

return 1;

case '*':

case '/':

return 2;

case '^':

return 3;

}// End of switch case

// -1 for invalid character

return -1;

}// End of method

// Method to perform operation based on the operator

public int performOperation(Stack<Integer> numbers,

Stack<Character> operations)

{

// Extracts top two elements from the stack

int second = numbers.pop();

int first = numbers.pop();

  

// Extracts operator from stack

char currentOperator = operations.pop();

  

// Checks the operator

switch (currentOperator)

{

case '+':

return second + first;

case '-':

return first - second;

case '*':

return second * first;

case '/':

if (second == 0)

throw new

UnsupportedOperationException

("Cannot divide by zero");

return first / second;

}// End of switch case

return 0;

}// End of method

// Method to check the parameter character

// returns true is the character is operator

// otherwise returns false

public boolean checkForOperator(char currentCharacter)

{

return (currentCharacter == '+' ||

currentCharacter == '-' ||

currentCharacter == '/' ||

currentCharacter == '*' ||

currentCharacter == '^');

}// End of method

// main method definition

public static void main(String[] pms)

{

// Scanner class object created

Scanner sc = new Scanner(System.in);

// Accepts an expression

System.out.print("Enter an expression: ");

String infixExpression = sc.nextLine();

  

InfixToPostfixEvaluate ipe = new

InfixToPostfixEvaluate();

  

// Calls the method to evaluate and display the result

System.out.println("\n Result: " +

ipe.evaluateExpression(infixExpression));

}// End of main method

}// End of class

Sample Output:

Enter an expression: 17 / (2 + 3) - 13

Result: -10