Skip to content

Instantly share code, notes, and snippets.

@agrawal-priyank
Created October 11, 2017 00:36
Show Gist options
  • Save agrawal-priyank/9031d4dc6b292e20b9c98f0d7762d134 to your computer and use it in GitHub Desktop.
Save agrawal-priyank/9031d4dc6b292e20b9c98f0d7762d134 to your computer and use it in GitHub Desktop.
Evaluate an Arithmetic expression using Stacks in Java.
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