-
Notifications
You must be signed in to change notification settings - Fork 40
Tri 3: Tech Talk week 2: Calculator
jm1021 edited this page May 9, 2022
·
1 revision
In Tech Talk 1 you should have made your own Stack. This will be an important Data Structure as you build a Calculator.
- In mathematics, an expression or mathematical expression is a finite combination of symbols that is well-formed according to rules that depend on the context.
- In computers, expression can be hard to calculate with precedence rules. In computer math we often convert strings into Reverse Polish Notation (RPN, 3 + 4 becomes 3 4 +) using the Shunting-yard algorithm. Review Wikipedia diagram and the code and you will see the need for a Stack.
// Takes tokens and converts to Reverse Polish Notation (RPN), this is one where the operator follows its operands.
private void tokensToReversePolishNotation () {
// contains final list of tokens in RPN
this.reverse_polish = new ArrayList<>();
// stack is used to reorder for appropriate grouping and precedence
Stack tokenStack = new Stack();
for (String token : tokens) {
switch (token) {
// If left bracket push token on to stack
case "(":
tokenStack.push(token);
break;
case ")":
while (tokenStack.peek() != null && !tokenStack.peek().equals("("))
{
reverse_polish.add( (String)tokenStack.pop() );
}
tokenStack.pop();
break;
case "+":
case "-":
case "*":
case "/":
case "%":
// While stack
// not empty AND stack top element
// and is an operator
while (tokenStack.peek() != null && isOperator((String) tokenStack.peek()))
{
if ( isPrecedent(token, (String) tokenStack.peek() )) {
reverse_polish.add((String)tokenStack.pop());
continue;
}
break;
}
// Push the new operator on the stack
tokenStack.push(token);
break;
default: // Default should be a number, there could be test here
this.reverse_polish.add(token);
}
}
// Empty remaining tokens
while (tokenStack.peek() != null) {
reverse_polish.add((String)tokenStack.pop());
}
}- Your calculator will need a driver for testing. In your driver, you will need to consider multiple conditions, for instance changes with precedence...
Calculator simpleMath = new Calculator("100 + 200 * 3");
System.out.println("Simple Math\n" + simpleMath);
Calculator parenthesisMath = new Calculator("(100 + 200) * 3");
System.out.println("Parenthesis Math\n" + parenthesisMath);
Calculator allMath = new Calculator("200 % 300 + 5 + 300 / 200 + 1 * 100");
System.out.println("All Math\n" + allMath);
Calculator allMath2 = new Calculator("200 % (300 + 5 + 300) / 200 + 1 * 100");
System.out.println("All Math2\n" + allMath2);- To support mathematical expressions you need to define Data Structures to define operators
// Helper definition for supported operators
private final Map<String, Integer> OPERATORS = new HashMap<>();
{
// Map<"token", precedence>
OPERATORS.put("*", 3);
OPERATORS.put("/", 3);
OPERATORS.put("%", 3);
OPERATORS.put("+", 4);
OPERATORS.put("-", 4);
}- To support terms or tokens in mathematical expression you need to define symbols (other than operators) that split terms of expression
// Helper definition for supported operators
private final Map<String, Integer> SEPARATORS = new HashMap<>();
{
// Map<"separator", not_used>
SEPARATORS.put(" ", 0);
SEPARATORS.put("(", 0);
SEPARATORS.put(")", 0);
}- To work with these operators and separators you will need to test functions
// Test if token is an operator
private boolean isOperator(String token) {
// find the token in the hash map
return OPERATORS.containsKey(token);
}
// Test if token is an separator
private boolean isSeperator(String token) {
// find the token in the hash map
return SEPARATORS.containsKey(token);
}
// Compare precedence of operators.
private Boolean isPrecedent(String token1, String token2) {
// token 1 is precedent if it is greater than token 2
return (OPERATORS.get(token1) - OPERATORS.get(token2) >= 0) ;
}- After thinking about basic anatomy of an expression and RPN algorithm, we need to think of flow of control to go from terms/tokens, RPN, and ultimately calculate the final result. In this flow, a Class can be established to manage the Calculator object. The Constructor can receive an expression and establish a sequence to produce a result.
// Create a 1 argument constructor expecting a mathematical expression
public Calculator(String expression) {
// original input
this.expression = expression;
// parse expression into terms
this.termTokenizer();
// place terms into reverse polish notation
this.tokensToReversePolishNotation();
// calculate reverse polish notation
this.rpnToResult();
}- A Term tokenizer is used to change the String expression into a series of tokens that constitute distinct elements of a Mathematical expression.
// Term Tokenizer takes original expression and converts it to ArrayList of tokens
private void termTokenizer() {
// contains final list of tokens
this.tokens = new ArrayList<>();
int start = 0; // term split starting index
StringBuilder multiCharTerm = new StringBuilder(); // term holder
for (int i = 0; i < this.expression.length(); i++) {
Character c = this.expression.charAt(i);
if ( isOperator(c.toString() ) || isSeperator(c.toString()) ) {
// 1st check for working term and add if it exists
if (multiCharTerm.length() > 0) {
tokens.add(this.expression.substring(start, i));
}
// Add operator or parenthesis term to list
if (c != ' ') {
tokens.add(c.toString());
}
// Get ready for next term
start = i + 1;
multiCharTerm = new StringBuilder();
} else {
// multi character terms: numbers, functions, perhaps non-supported elements
// Add next character to working term
multiCharTerm.append(c);
}
}
// Add last term
if (multiCharTerm.length() > 0) {
tokens.add(this.expression.substring(start));
}
}- Write the remaining methods to support calculation, capture attributes, and establish a toString to output for the attributes.
// Key instance variables
private final String expression;
private ArrayList<String> tokens;
private ArrayList<String> reverse_polish;
private Double result;
// Print the expression, terms, and result
public String toString() {
return ("Original expression: " + this.expression + "\n" +
"Tokenized expression: " + this.tokens.toString() + "\n" +
"Reverse Polish Notation: " +this.reverse_polish.toString() + "\n" +
"Final result: " + String.format("%.2f", this.result));
}- Finally, here is sample output for the calculator
Simple Math
Original expression: 100 + 200 * 3
Tokenized expression: [100, +, 200, *, 3]
Reverse Polish Notation: [100, 200, 3, *, +]
Final result: 700.00
Parenthesis Math
Original expression: (100 + 200) * 3
Tokenized expression: [(, 100, +, 200, ), *, 3]
Reverse Polish Notation: [100, 200, +, 3, *]
Final result: 900.00
Fraction Math
Original expression: 100.2 - 99.3
Tokenized expression: [100.2, -, 99.3]
Reverse Polish Notation: [100.2, 99.3, -]
Final result: 0.90
Modulo Math
Original expression: 300 % 200
Tokenized expression: [300, %, 200]
Reverse Polish Notation: [300, 200, %]
Final result: 100.00
Division Math
Original expression: 300/200
Tokenized expression: [300, /, 200]
Reverse Polish Notation: [300, 200, /]
Final result: 1.50
Multiplication Math
Original expression: 300 * 200
Tokenized expression: [300, *, 200]
Reverse Polish Notation: [300, 200, *]
Final result: 60000.00
All Math
Original expression: 200 % 300 + 5 + 300 / 200 + 1 * 100
Tokenized expression: [200, %, 300, +, 5, +, 300, /, 200, +, 1, *, 100]
Reverse Polish Notation: [200, 300, %, 5, +, 300, 200, /, +, 1, 100, *, +]
Final result: 306.50
All Math2
Original expression: 200 % (300 + 5 + 300) / 200 + 1 * 100
Tokenized expression: [200, %, (, 300, +, 5, +, 300, ), /, 200, +, 1, *, 100]
Reverse Polish Notation: [200, 300, 5, +, 300, +, %, 200, /, 1, 100, *, +]
Final result: 101.00
All Math3
Original expression: 200%(300+5+300)/200+1*100
Tokenized expression: [200, %, (, 300, +, 5, +, 300, ), /, 200, +, 1, *, 100]
Reverse Polish Notation: [200, 300, 5, +, 300, +, %, 200, /, 1, 100, *, +]
Final result: 101.00
- Build a calculator to process expressions and ultimately change RPN to a calculation.
// Takes RPN and produces a final result
private void rpnToResult()
{
// Stack used to hold calculation while process RPN
Stack calculation = new Stack();
// for loop to process RPN
{
// If the token is a number
{
// Push number to stack
}
// else
{
// Pop the two top entries
// Based off of Token operator calculate result
// Push result back onto the stack
}
}
// Pop final result and set as final result for expression
}- Build in Power of operator ^: 2 ^ 1 = 2, 2 ^ 2 = 4, 2 ^ 3 = 8
- Extra credit. Build variable assignment and evaluation into your expressions (a = 2; a + 1).
- Extra credit. Investigate Wikipedia article and pseudo code and try adding a SQRT(). Try building Pythagoras expression.