2019 FRQ
2019 FRQ
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
import java.lang.Math;
import java.lang.Double;
public class Operator {
// Key instance variables
private String expression;
private Double result = 0.0;
private ArrayList<String> tokens;
private ArrayList<String> reverse_polish;
// Helper definition for supported operators
private final Map<String, Integer> OPERATORS = new HashMap<>();
{
// Map<"token", precedence>
OPERATORS.put("POW", 1);
OPERATORS.put("RT", 2);
OPERATORS.put("^", 2);
OPERATORS.put("*", 3);
OPERATORS.put("/", 3);
OPERATORS.put("%", 3);
OPERATORS.put("+", 4);
OPERATORS.put("-", 4);
}
// 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);
}
// Create a 1 argument constructor expecting a mathematical expression
public Operator(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();
}
// 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) ;
}
// 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() ) || isSeparator(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));
}
}
// 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<String> tokenStack = new Stack<String>();
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( tokenStack.pop() );
}
tokenStack.pop();
break;
case "RT":
case "+":
case "-":
case "*":
case "/":
case "%":
case "^":
case "POW":
// While stack
// not empty AND stack top element
// and is an operator
while (tokenStack.size() > 0 && isOperator(tokenStack.peek()))
{
if ( isPrecedent(token, tokenStack.peek() )) {
reverse_polish.add(tokenStack.pop());
continue;
}
break;
}
// Push the new operator on the stack
tokenStack.push(token);
break;
case "lbs":
case "LBS":
case "Lbs":
// recognize pi variable and replace that token with it
this.reverse_polish.add("2.2");
break;
case "cm":
case "Cm":
case "CM":
this.reverse_polish.add("2.54");
break;
default:
try
{
Double.parseDouble(token);
}
catch(NumberFormatException e)
{
// Resolve variable to 0 in order for the rest of the function to successfully run.
this.reverse_polish.add("0");
this.expression = "Error with parsing your expression \'" + this.expression + "\'. Please enter valid numbers, operators, or variables and try again.";
break;
}
this.reverse_polish.add(token);
}
}
// Empty remaining tokens
while (tokenStack.size() > 0) {
reverse_polish.add(tokenStack.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 top two entries
double a = calcStack.pop();
double b = calcStack.pop();
// Calculate intermediate results
switch (token) {
// b goes first, as it is popped second and must be on the left to make the equation work
case "RT":
// rt is the only exception as the first value is the value of the root being done to the second value
result = Math.pow(a, (1/b));
break;
case "+":
result = b + a;
break;
case "-":
result = b - a;
break;
case "*":
result = b * a;
break;
case "/":
result = b / a;
break;
case "%":
result = b % a;
break;
case "^":
case "POW":
result = Math.pow(b,a);
break;
default:
break;
}
// Pop the two top entries
// 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();
}
public String calcToString(boolean x) {
if (x) {
System.out.println("");
System.out.println("Result: " + this.expression + " = " + this.result);
System.out.println("Tokens: " + this.tokens + " , RPN: " + this.reverse_polish);
}
String output = this.expression + " = " + this.result;
return output;
}
public String jsonify() {
String json = "{ \"Expression\": \"" + this.expression + "\", \"Tokens\": \"" + this.tokens + "\", \"RPN\": \"" + this.reverse_polish + "\", \"Result\": " + this.result + " }";
return json;
}
}
// Testing different outputs
String result = " ";
// Should print 8
Operator aa = new Operator("2 * 7 + 4");
result = aa.calcToString(true);
// Operator bb = new Operator("2 * ( 2 + 4 )");
// result = bb.calcToString(true);
// Should print 2.
Operator cc = new Operator("( 6 + 19 ) / 3");
result = cc.calcToString(true);
// Should print 14
Operator dd = new Operator("15 % 5 * 7");
result = dd.calcToString(true);
// EXPONENTS
Operator ee = new Operator("3 + 5 ^ 2");
result = ee.calcToString(true);
// ROOT FUNCTION
Operator ff = new Operator("3 + 7 RT 100");
result = ff.calcToString(true);
// ROOT FUNCTION WITH PARENTHESES
Operator gg = new Operator("2 RT ( 3 + 6 +16 )");
result = gg.calcToString(true);
Operator hh = new Operator("lbs * 1");
result = hh.calcToString(true);
Operator hh = new Operator("lbs * 60");
result = hh.calcToString(true);
Operator ii = new Operator("cm * 2");
result = ii.calcToString(true);
Operator ii = new Operator("cm * 1");
result = ii.calcToString(true);