FRQ3 - Array/ArrayList
Relationship of FRQ 3 to a Project Based learning exercise.
// Helper definition to define operators, lookup in MAP are fast and easy O(1) versus ArrayList O(n)
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);
}
Organizing an Expression
To support terms in mathematical expression you need to define symbols (other than operators) that help delineate the elements of an expression. Ultimately, the String expression will be broken in distinct elements in a List, we will call each element a Token.
-
FRQ3 calls these delimiters. Many encoded strings contain delimiters. A delimiter is a non-empty string that acts as a boundary between different parts of a larger string. The delimiters involved in this question occur in pairs that must be balanced,with each pair having an open delimiter and a close delimiter.
-
FRQ3 mentions expressions. Expressions in mathematics use open parentheses "(" and close parentheses ")" as delimiters. For each open parenthesis, there must be a matching close parenthesis.
- (x + y) * 5 is a valid mathematical expression.
- (x + (y) is NOT a valid mathematical expression because there are more open delimiters than close delimiters.
// Helper definition for supported separators
private final Map<String, Integer> SEPARATORS = new HashMap<>();
{
// Map<"separator", not_used>
SEPARATORS.put(" ", 0);
SEPARATORS.put("(", 0);
SEPARATORS.put(")", 0);
}
// 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 isSeparator(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) ;
}
Calculator Theory
Mathematical expression written by humans are in the form of a String Expression. Since this expression is simply a string to the computer... an algorithm is required to reform the equation for the computer to ensure it interprets expression according to the rules of mathematics.
- In mathematics, an expression or mathematical expression is a finite combination of symbols that is well-formed (ie "100 + 200").
- In computers, a string expression is hard to calculate. Thus, the expression needs to be restructured according to rules of Mathematics that a computer can calculate. For instance, the order of precedence rules, aka PEMDAS (parenthesis, exponents, multiplication, division, addition, subtraction) need to be factored into order of computation. To support these rules, in computer math we often convert a String expression into Reverse Polish Notation (RPN). This converts a simple string like "3 + 4" to become ["100", "200", "+"]) using the Shunting-yard algorithm.
String expression to calculation will need a flow of control. A Class (aka model) is defined with instance variables, one argument constructor, and a toString. In this code, the flow is in the Calculator calculation is contained in the constructor.
- Capture original input
- Parse expression into mathematical terms
- If using Shunting-yard algorithm, place terms into RPN
- Calculate RPN to a result
// Key instance variables
private final String expression;
private ArrayList<String> tokens;
private ArrayList<String> reverse_polish;
private Double result;
// Create a 1 argument constructor providing 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();
}
// 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));
}
Term Tokenizer
FRQ3 talks about changing terms to tokens. A string containing text and possibly delimiters has been split into tokens and stored in String[] tokens. Each token is either an open delimiter, a close delimiter, or a substring that is not a delimiter. You will write the method getDelimitersList, which returns an ArrayList containing all the open and close delimiters found in tokens in their original order.
- openDel:"(" - closeDel: ")" - tokens: "(" "100 + 200" ")" " * 3" - ArrayList of delimiters: "(" ")"The method termTokenizer() is used to change the String expression into a series of tokens that constitute distinct elements of a Mathematical expression. The result is retained in the ArrayList "tokens". Every token, including parenthesis, is an element in the "tokens" ArrayList.
- Example 1:Simple Math - Original expression: 100 + 200 * 3 - tokens ArrayList: [100, +, 200, *, 3] - Example 2: Parenthesis Math to change order of operations - Original expression: (100 + 200) * 3 - tokens ArrayList: [(, 100, +, 200, ), *, 3]
// 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));
}
}
Tokens to RPN
Before calculation the tokens need to be turned into RPN. This puts math in left to right order and resolves order of operations.
- Simple Math.
- Tokens:"100", "+", "200", "", "3" - RPN: "100", "200", "3", "", "+"
- Parenthesis Math. Note RPN difference
- Tokens: "(", "100}, "+", "200", ")", "*", "3"
- RPN: "100", "200", "+", "3", "*"
// Takes tokens and converts to Reverse Polish Notation (RPN).
private void tokensToReversePolishNotation () {
// contains final list of tokens in RPN
List<String> 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());
}
}
RPN to Result
Below is setup/pseudo code to produce a result. This is opportunity to learn about a Stack, by adding and removing elements from the stack according to intermediate and final results.
During calculation algorithm will work through RPN, Left to Right. 1. go to first operator, 2. obtain to the amount of operands required for operator, 3. solve, 4. push result
-
Simple Math.
- RPN:"100", "200", "3", "*", "+" - calcStack Step 1: [100]
- calcStack Step 2 [200, 100]
- calcStack Step 3 [3, 200, 100]
- calcStack Step 4 [600, 100]
-
calcStack Step 5 [700]
result = 700 # final pop
// Takes RPN and produces a final result
private void rpnToResult()
{
// stack is used to hold operands and each calculation
Stack<Double> calcStack = new Stack<Double>();
// RPN is processed, ultimately calcStack has final result
for (String token : this.reverse_polish)
{
// If the token is an operator, calculate
if (isOperator(token))
{
// Pop the two top entries
// Calculate intermediate results
result = 0.0;
// Push intermediate result back onto the stack
calcStack.push( result );
}
// else the token is a number push it onto the stack
else
{
calcStack.push(Double.valueOf(token));
}
}
// Pop final result and set as final result for expression
this.result = calcStack.pop();
}
Output Examples
Here are sample outputs for the calculator
Simple Math
Original expression:100 + 200 * 3Tokenized 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
Decimal 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
Hacks
Build a calculator to process expressions and ultimately change RPN to a calculation.
- Finish rpnToResult for Calculator
- Add unbalanced parenthesis check and in original FRQ, or other error checks. FYI, usually when structuring code with error checking it can greatly impact code structure.
- Build in Power of operator ^:2 ^ 1 = 2, 2 ^ 2 = 4, 2 ^ 3 = 83. Build an API to receive an expression and respond with a result. This is a good opportunity to respond with an error if you built in parenthesis or other error checking.
Advanced. Deeper parsing and evaluation.
- Try adding single argument function SQRT. This should be combined with ()'s to make sense, SQRT(expression). Though "SQRT 1" could work.
- Build variable into expression "a = 3; b + 4; SQRT(a^2 + b^2)". Hint... build a HashMap for variables.
- At this point you probably have Physics and Calculus possibilities for managing and modeling equations.
Advanced. Deployment and Frontend.
- Deploy all of your APIs to Team Backend repo.
- Start making Frontend pages to interact with APIs.
Advanced. Try other evaluations or use cases of parsing Strings to Tokens.
- Make a Tokenizer for sentences to words.
- Count words, count punctuation.
- Find definitions for Words or Translations.
Basic Skill building, do FRQ3. FYI, isBalanced could help in error corrections for Calculator.
public class Delimiters private String openDel private String closeDel public Delimiters(String open, String close) public ArrayList<String> getDelimitersList(String[] tokens) public boolean isBalanced(ArrayList<String> delimiters)