Created
October 11, 2017 00:36
-
-
Save agrawal-priyank/9031d4dc6b292e20b9c98f0d7762d134 to your computer and use it in GitHub Desktop.
Evaluate an Arithmetic expression using Stacks in Java.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Stack; | |
public class Calculator { | |
public enum Operator{ADD, SUBTRACT, MULTIPLY, DIVIDE, BLANK} | |
public static void main(String[] args){ | |
String expression = "2-6-7*8/2+5"; | |
Calculator calc = new Calculator(); | |
System.out.println(calc.compute(expression)); | |
} | |
public double compute(String sequence){ | |
Stack<Double> numberStack = new Stack<Double>(); | |
Stack<Operator> operatorStack = new Stack<Operator>(); | |
for(int i = 0; i < sequence.length(); i++){ | |
try{ | |
int number = parseNumber(sequence, i); | |
numberStack.push((double)number); | |
i += Integer.toString(number).length(); | |
if(i >= sequence.length()){ | |
break; | |
} | |
Operator op = parseOperator(sequence, i); | |
collapseTop(numberStack, operatorStack, op); | |
operatorStack.push(op); | |
} catch(NumberFormatException ex){ | |
return Integer.MIN_VALUE; | |
} | |
} | |
collapseTop(numberStack, operatorStack, Operator.BLANK); | |
if(numberStack.size() == 1 && operatorStack.size() == 0){ | |
return numberStack.pop(); | |
} | |
return 0; | |
} | |
private void collapseTop(Stack<Double> numberStack, Stack<Operator> operatorStack, Operator futureTop){ | |
while(numberStack.size() >= 2 && operatorStack.size() >= 1){ | |
if(priorityOfOperator(futureTop) <= priorityOfOperator(operatorStack.peek())){ | |
double second = numberStack.pop(); | |
double first = numberStack.pop(); | |
Operator op = operatorStack.pop(); | |
double result = applyOp(first, op, second); | |
numberStack.push(result); | |
} else{ | |
break; | |
} | |
} | |
} | |
private double applyOp(double left, Operator op, double right){ | |
switch (op){ | |
case ADD: return left + right; | |
case SUBTRACT: return left - right; | |
case MULTIPLY: return left * right; | |
case DIVIDE: return left / right; | |
default: return right; | |
} | |
} | |
private int priorityOfOperator(Operator op){ | |
switch (op){ | |
case ADD: return 1; | |
case SUBTRACT: return 1; | |
case MULTIPLY: return 2; | |
case DIVIDE: return 2; | |
case BLANK: return 0; | |
} | |
return 0; | |
} | |
private int parseNumber(String sequence, int offset){ | |
StringBuilder sb = new StringBuilder(); | |
while(offset < sequence.length() && Character.isDigit(sequence.charAt(offset))){ | |
sb.append(sequence.charAt(offset)); | |
offset++; | |
} | |
return Integer.parseInt(sb.toString()); | |
} | |
private Operator parseOperator(String sequence, int offset){ | |
if(offset < sequence.length()){ | |
char op = sequence.charAt(offset); | |
switch (op){ | |
case '+': return Operator.ADD; | |
case '-': return Operator.SUBTRACT; | |
case '*': return Operator.MULTIPLY; | |
case '/': return Operator.DIVIDE; | |
} | |
} | |
return Operator.BLANK; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment