Question

SOLUTION IN JAVA

In this problem, we will be evaluating simple math expressions that contain numbers, +, *, (, and ). Specifically, you will write a function that takes in a string representing an expression and returns an integer representing its result. The input string will not contain any spaces. The following are examples of input and corresponding output:

Input:

3+5

Output:

8

Input:

3+5*7

Output:

38

Input:

3*(5*(7+2))

Output:

135

The functionality for reading and printing answers is written in the class Main; your task is to complete the eval() method which takes in a string representing an arithmetic expression as described above and outputs a single integer representing the result of this expression. (Hint: Parentheses are only used in the second half of the test cases.)

You may import stuff from java.util, but that's it. Examples would be Stack, ArrayList, etc.

Answer 1

/* I have already given this answer before and it's working with n digit also */

import java.util.Scanner;
import java.util.Stack;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

// read input
String expression = sc.nextLine();

// print the evaluated result
System.out.println(eval(expression));
}

public static int eval(String expression) {
//Stack for Numbers
Stack numbers = new Stack<>();

//Stack for operators
Stack operations = new Stack<>();
for(int i=0; i char c = expression.charAt(i);
//check if it is number
if(Character.isDigit(c)){
//Entry is Digit, it could be greater than one digit number
int num = 0;
while (Character.isDigit(c)) {
num = num*10 + (c-'0');
i++;
if(i < expression.length())
c = expression.charAt(i);
else
break;
}
i--;
//push it into stack
numbers.push(num);
}else if(c=='('){
//push it to operators stack
operations.push(c);
}
//Closed brace, evaluate the entire brace
else if(c==')') {
while(operations.peek()!='('){
int output = performOperation(numbers, operations);
//push it back to stack
numbers.push(output);
}
operations.pop();
}
// current character is operator
else if(isOperator(c)){
//1. If current operator has higher precedence than operator on top of the stack,
//the current operator can be placed in stack
// 2. else keep popping operator from stack and perform the operation in numbers stack till
//either stack is not empty or current operator has higher precedence
//than operator on top of the stack
while(!operations.isEmpty() && precedence(c) int output = performOperation(numbers, operations);
//push it back to stack
numbers.push(output);
}
//now push the current operator to stack
operations.push(c);
}
}
//If here means entire expression has been processed,
//Perform the remaining operations in stack to the numbers stack

while(!operations.isEmpty()){
int output = performOperation(numbers, operations);
//push it back to stack
numbers.push(output);
}
return numbers.pop();
}
static int precedence(char c){
switch (c){
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}

public static int performOperation(Stack numbers, Stack operations) {
int a = numbers.pop();
int b = numbers.pop();
char operation = operations.pop();
switch (operation) {
case '+':
return a + b;
case '-':
return b - a;
case '*':
return a * b;
case '/':
if (a == 0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return b / a;
}
return 0;
}

public static boolean isOperator(char c){
return (c=='+'||c=='-'||c=='/'||c=='*'||c=='^');
}
}

/* OUTPUT */