Last active
September 25, 2016 12:35
-
-
Save chaoyangnz/accd5f26db934cf90e8d1914efc84d5a to your computer and use it in GitHub Desktop.
This file contains 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 org.junit.Test; | |
import java.util.ArrayList; | |
import java.util.List; | |
import java.util.Stack; | |
/** | |
* Expression Calculator | |
*/ | |
public class ExpressionCalculator { | |
private final Stack<Operand> operandStack = new Stack<Operand>(); | |
private final Stack<Operator> operatorStack = new Stack<Operator>(); // possible: operator or left bracket | |
/** | |
* pop operator and calculate it, then save result to operand stack | |
*/ | |
private void calculate() { | |
Operator operator = (Operator) operatorStack.pop(); | |
Operand operand2 = operandStack.pop(); | |
Operand operand1 = operandStack.pop(); | |
int result = operator.calculate(operand1, operand2); | |
operandStack.push(Operand.valueOf(result)); | |
} | |
/** | |
* calculate the entire expression | |
* | |
* @param infix | |
* @return | |
*/ | |
public double calculate(Element[] infix) { | |
for(Element element : infix) { | |
// System.out.print("=> "); | |
// ArrayUtil.print(operandStack.toArray()); | |
// System.out.print("<= "); | |
// ArrayUtil.print(operatorStack.toArray()); | |
// System.out.println(); | |
if(element instanceof Operand) { | |
Operand operand = (Operand) element; | |
operandStack.push(operand); | |
} | |
else if(element == Operator.LEFT_BRACKET) { | |
Operator leftBrace = (Operator) element; | |
operatorStack.push(leftBrace); | |
} | |
else if(element == Operator.RIGHT_BRACKET) { // right bracket | |
boolean leftBracketFound = false; | |
while (!operatorStack.empty()) { | |
Operator top = operatorStack.peek(); | |
if(top != Operator.LEFT_BRACKET) { | |
calculate(); | |
} else { | |
leftBracketFound = true; | |
operatorStack.pop(); // remove left bracket | |
break; | |
} | |
} | |
if(!leftBracketFound) { | |
throw new IllegalArgumentException("cannot find left brace for a right brace"); | |
} | |
} | |
else { // Operator | |
Operator operator = (Operator) element; | |
while (!operatorStack.empty()) { | |
Operator top = operatorStack.peek(); | |
if(operator.priority <= top.priority) { | |
calculate(); | |
} else { | |
break; | |
} | |
} | |
operatorStack.push(operator); | |
} | |
} | |
while (!operatorStack.empty()) { | |
calculate(); | |
} | |
return operandStack.pop().value; | |
} | |
/** | |
* get its postfix expression | |
* | |
* @param infix | |
* @return | |
*/ | |
public Element[] postfix(Element[] infix) { | |
List<Element> postfix = new ArrayList<Element>(); | |
for (Element element : infix) { | |
if(element instanceof Operand) { | |
postfix.add(element); | |
} | |
else if(element == Operator.LEFT_BRACKET) { | |
operatorStack.push((Operator)element); | |
} | |
else if(element == Operator.RIGHT_BRACKET) { | |
boolean leftBracketFound = false; | |
while (!operatorStack.empty()) { | |
Operator top = operatorStack.peek(); | |
if(top != Operator.LEFT_BRACKET) { | |
operatorStack.pop(); | |
postfix.add(top); | |
} else { | |
leftBracketFound = true; | |
operatorStack.pop(); // remove left bracket | |
break; | |
} | |
} | |
if(!leftBracketFound) { | |
throw new IllegalArgumentException("cannot find left brace for a right brace"); | |
} | |
} | |
else if(element instanceof Operator) { | |
Operator operator = (Operator) element; | |
while (!operatorStack.empty()) { | |
Operator top = operatorStack.peek(); | |
if(operator.priority <= top.priority) { // * - | |
operatorStack.pop(); | |
postfix.add(top); | |
} else { | |
break; | |
} | |
} | |
operatorStack.push(operator); | |
} | |
} | |
while (!operatorStack.empty()) { | |
postfix.add(operatorStack.pop()); | |
} | |
return postfix.toArray(new Element[postfix.size()]); | |
} | |
public double calculatePostfix(Element[] postfix) { | |
for(Element element : postfix) { | |
if(element instanceof Operand) { | |
operandStack.push((Operand) element); | |
} | |
else if(element instanceof Operator) { | |
operatorStack.push((Operator) element); | |
calculate(); | |
} | |
} | |
return operandStack.pop().value; | |
} | |
private static abstract class Element {} | |
private static class Operand extends Element { | |
int value; | |
private Operand(int value) { this. value = value; } | |
public static Operand valueOf(int value) { | |
return new Operand(value); | |
} | |
public String toString() { | |
return String.valueOf(value); | |
} | |
} | |
private static class Operator extends Element { | |
public final static Operator PLUS = new Operator('+', 1, 2); | |
public final static Operator MINUS = new Operator('-', 1, 2); | |
public final static Operator MULTIPLY = new Operator('*', 2, 2); | |
public final static Operator DIVIDE = new Operator('/', 2, 2); | |
public final static Operator MODULO = new Operator('%', 2, 2); | |
public final static Operator LEFT_BRACKET = new Operator('(', 0, 0); | |
public final static Operator RIGHT_BRACKET = new Operator(')', 100, 0); | |
char value; | |
int priority; | |
int operandCount; | |
private Operator(char value, int priority, int operands) { | |
this.value = value; | |
this.priority = priority; | |
this.operandCount = operands; | |
} | |
public int calculate(Operand...operands) { | |
assert operands != null && operands.length == operandCount; | |
if(this.value == '+') return operands[0].value + operands[1].value; | |
if(this.value == '-') return operands[0].value - operands[1].value; | |
if(this.value == '*') return operands[0].value * operands[1].value; | |
if(this.value == '/') return operands[0].value / operands[1].value; | |
if(this.value == '%') return operands[0].value % operands[1].value; | |
throw new UnsupportedOperationException("unsupported operator"); | |
} | |
public static Operator valueOf(char value) { | |
if(value == '+') return PLUS; | |
if(value == '-') return MINUS; | |
if(value == '*') return MULTIPLY; | |
if(value == '/') return DIVIDE; | |
if(value == '%') return MODULO; | |
if(value == '(') return LEFT_BRACKET; | |
if(value == ')') return RIGHT_BRACKET; | |
throw new UnsupportedOperationException("unsupported operator"); | |
} | |
public String toString() { | |
return String.valueOf(value); | |
} | |
} | |
public static Element[] fromString(String expression) { | |
char[] chars = expression.toCharArray(); | |
Element[] elements = new Element[chars.length]; | |
for(int i = 0; i < chars.length; ++i) { | |
char ch = chars[i]; | |
if(Character.isDigit(ch)) { | |
elements[i] = Operand.valueOf(Integer.parseInt(String.valueOf(ch))); | |
} else { | |
elements[i] = Operator.valueOf(ch); | |
} | |
} | |
return elements; | |
} | |
public static void print(Element[] elements) { | |
for(int i=0; i < elements.length; ++i) { | |
System.out.print(elements[i]); | |
} | |
System.out.println(); | |
} | |
@Test | |
public void test() { | |
Element[] infix1 = fromString("5-(5-3*1+4)-6/3*4"); | |
print(infix1); | |
System.out.println(calculate(infix1)); | |
Element[] postfix1 = postfix(infix1); | |
print(postfix1); | |
System.out.println(calculatePostfix(postfix1)); | |
Element[] infix2 = fromString("5-(5-3*1+4)-(6/3*(8/2-3)-4)"); | |
print(infix2); | |
System.out.println(calculate(infix2)); | |
Element[] postfix2 = postfix(infix2); | |
print(postfix2); | |
System.out.println(calculatePostfix(postfix2)); | |
Element[] infix3 = fromString("5-(5-3*1+4)-(6/3*(8%3-3)-4)"); | |
print(infix3); | |
System.out.println(calculate(infix3)); | |
Element[] postfix3 = postfix(infix3); | |
print(postfix3); | |
System.out.println(calculatePostfix(postfix3)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment