I hate it, I really hate it... I hate meee, why???? 😭🥵😪
So I'm getting now the correct results. I'm getting the correct number of calculations, too. What else does CG want. Do they again have some totally weird solution in mind that you need to follow to the point?
The last thing it might be here may be the exponent. Do the really want me to treat 2^4 as 2*2*2*2? 3 operations instead of one? If so then I want start to fiddle that next exception into the code. I could have solved that in half the code lines but with all that fiddling and pressing into recursin with that exact number of operations they are stepping onto my nerves like crazy. Ridiculous... that's just ridiculous.
Next task that is making me want to give up this course (me cursing like crazy: @*#%!$)
package com.codegym.task.task34.task3404;
/*
Recursion for mathematical expressions
*/
/*
first thoughts: this one is tough...
after searching the web I found out about shunting yard algorithm. That seems some practical way. However it is not
meant to be pressed into a recurse method. It is linear and works perfect with stacks.
So what I'm going to do:
a) I implement a shunting-yard algorithm
b) the passed string to the recurse method I'll convert to the reverse polish notation (if not already done - use a
sentinel for that like starting the string with >>> or |-> or whatever)
c) convert the string to a stack
d) check the abort condition, if there is only one operand left
e) the next step is to do one and only one calculation
f) pass the result of that one calculation and eventual operands on the to do stack back onto the stack
g) and convert back to a string
h) recurse
*/
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
//solution.recurse("sin(2*(-5+1.5*4)+28)", 0); // Expected output: 0.5 6
solution.recurse("tan(2025 ^ 0.5)", 0);
solution.recurse("sin(2*(-5+1.5*4)+28)", 0);
solution.recurse("2 + -3*2", 0);
}
public void recurse(final String expression, int countOperation) {
LinkedList<String> parsedExpression = parse(expression);
// abort condition
if (parsedExpression.size() <= 2) {
// System.out.print(new BigDecimal(parsedExpression.get(1)).setScale(2, RoundingMode.HALF_UP).doubleValue());
//System.out.format("%.1f", Double.parseDouble(parsedExpression.get(1)));
// System.out.println(" " + countOperation);
double d = Double.parseDouble(parsedExpression.get(1));
NumberFormat numberFormat = NumberFormat.getNumberInstance(Locale.ENGLISH);
numberFormat.setRoundingMode(RoundingMode.HALF_EVEN);
DecimalFormat df = (DecimalFormat) numberFormat;
df.applyPattern("#.##");
String stringWeNeed = df.format(d);
System.out.println(stringWeNeed + " " + countOperation);
return;
}
LinkedList<String> rpn = createRPL(parsedExpression);
LinkedList<String> stack = new LinkedList<>();
// build a map with all operator symbols
Map<String, Operator> ops = new HashMap<>();
for (Operator operator : Operator.values())
ops.put(operator.symbol, operator);
// do one calculation,
// pack everything together again in a String and recurse
while(!rpn.isEmpty()) {
// if the current element on the rpn stack is a operator, pop it and do the math
if (ops.containsKey(rpn.peek())) {
// to calculate we need to know which operator it is and how many operands it needs... so we just pass the
// operands stack to the calc method
// the result we pop onto the operands stack again and push all elements of it onto the rpn stack
// finally we create a string from that stack and recurse
calculate(stack, ops.get(rpn.pop()));
// we did one calculation... normally we would just continue here to calc but recursion is asked...
// so break out of the loop
break;
} else
stack.push(rpn.pop());
}
// move all the operands on the operands stack back to the rpn stack so that we can rebuild the expression from there
while(!stack.isEmpty())
rpn.push(stack.pop());
// create the string from the rpn stack
StringBuilder sb = new StringBuilder("|>>>"); // and add the marker that initial parsing already has been done
while (!rpn.isEmpty())
sb.append(rpn.pop()).append(" ");
recurse(sb.toString().trim(), ++countOperation);
}
/**
* takes operands from the stack and does the math, the results gets pushed onto the stack again
* @param stack
* @param op
*/
private static void calculate(LinkedList<String> stack, Operator op) {
double opB = Double.parseDouble(stack.pop());
double result;
switch (op) {
case ADDITION :
result = Double.parseDouble(stack.pop()) + opB;
break;
case SUBTRACTION:
result = Double.parseDouble(stack.pop()) - opB;
break;
case MULTIPLICATION:
result = Double.parseDouble(stack.pop()) * opB;
break;
case DIVISION:
result = Double.parseDouble(stack.pop()) / opB;
break;
case MODULUS:
result = Double.parseDouble(stack.pop()) % opB;
break;
case POWER:
result = Math.pow(Double.parseDouble(stack.pop()), opB);
break;
case SQUARE_ROOT:
result = Math.sqrt(opB);
break;
case SINUS:
result = Math.sin(Math.toRadians(opB));
break;
case TANGENS:
result = Math.tan(Math.toRadians(opB));
break;
case COSINUS:
result = Math.cos(Math.toRadians(opB));
break;
case MAXIMUM:
result = Math.max(Double.parseDouble(stack.pop()),opB);
break;
default:
throw new IllegalArgumentException("operator not recognized");
}
stack.push(String.valueOf(result));
}
private static boolean isDigit(char c) {
return c >= '0' && c <= '9' || c == '.';
}
/**
* Create reverse polish notation from a LinkedList containing a (already parsed) expression
* @param tokens
* @return
*/
private static LinkedList<String> createRPL(LinkedList<String> tokens) {
// this method should run only once... so we need to use some marker inside the tokens stack
if (tokens != null && tokens.size() > 0)
if (tokens.peek().equals("|>>>")) {
tokens.pop();
return tokens;
}
LinkedList<String> output = new LinkedList<>();
LinkedList<String> stack = new LinkedList<>();
// build a map with all operator symbols
Map<String, Operator> ops = new HashMap<>();
for (Operator operator : Operator.values())
ops.put(operator.symbol, operator);
// build the reverse polish notation
for (String token : tokens) {
// do we have an operator?
if (ops.containsKey(token)) {
// Token is an operator
while (!stack.isEmpty() && ops.containsKey(stack.peek())) {
// While there is an operator (y) at the top of the operators stack and
// either (x) is left-associative and its precedence is less or equal to
// that of (y), or (x) is right-associative and its precedence
// is less than (y)
Operator cOp = ops.get(token); // Current operator
Operator lOp = ops.get(stack.peek()); // Top operator from the stack
if ((cOp.associativity == ASSOCIATIVITY.LEFT && cOp.comparePrecedence(lOp) <= 0) ||
(cOp.associativity == ASSOCIATIVITY.RIGHT && cOp.comparePrecedence(lOp) < 0)) {
// Pop (y) from the stack
// Add (y) output buffer
output.add(stack.pop());
continue;
}
break;
}
// Push the new operator on the stack
stack.push(token);
} else if ("(".equals(token)) {
// token is left parenthesis -> push it on the stack
stack.push(token);
} else if (")".equals(token)) {
// token is left parenthesis
while (!stack.isEmpty() && !stack.peek().equals("(")) {
// Until the top token (from the stack) is left parenthesis, pop from
// the stack to the output buffer
output.add(stack.pop());
}
// Also pop the left parenthesis but don't add to the output
stack.pop();
} else {
// a number, add it to the ouput
output.add(token);
}
}
// finally push stack to output
while (!stack.isEmpty())
output.add(stack.pop());
return output;
}
/**
* parses a passed string to a list, keeps unary -, + each number or operator (including brackets) have a new index
* @param expression
* @return a LinkedList that can be used as Stack for creating the reverse polish notation
*/
private static LinkedList<String> parse(String expression) {
// if we did the initial parsing and the string is already in RPL, just remove the marker and split it
if (expression.startsWith("|>>>")) {
LinkedList<String> tokens = new LinkedList<>(Arrays.asList(expression.substring(4).trim().split("\\s+")));
// add the marker
tokens.push("|>>>");
return tokens;
}
// initial parsing necessary:
// do some cleanup, remove all spaces and replace tan with t, sin with s.... add an end sentinel |
String s = expression.replaceAll("sin", "s")
.replaceAll("cos", "c")
.replaceAll("tan", "t")
.replaceAll("max", "m")
.replaceAll("sqrt", "q")
.replaceAll("\\p{Blank}", "");
s += "|";
StringBuilder sb = new StringBuilder(s);
char current = ' ';
char lastOp = '|';
int pos = 0;
/*
// parses unary minus as -number
while (current != '|') { // check for the end sentinel so we do not need to take care of the length
current = sb.charAt(pos);
if (!isDigit(current)) {
// unary -, +, don't add a space, don't treat as unary if a ) is before the +,-
if ((current == '+' || current == '-') && lastOp != ' ' && lastOp != ')') {
lastOp = ' '; // last is a number (not really necessary as digits are following an it's set there anyway)
pos++;
} else {
lastOp = current; // last is an operator
pos++;
sb.insert(pos++, ' ');
}
} else {
while (isDigit(current)) // as long as there are digits, advance
current = sb.charAt(++pos);
sb.insert(pos++, ' ');
lastOp = ' '; // last is a number
}
}
*/
// parses unary minus as -1 * number (so that the counts match)
while (current != '|') { // check for the end sentinel so we do not need to take care of the length
current = sb.charAt(pos);
if (!isDigit(current)) {
// unary -, +, don't add a space, don't treat as unary if a ) is before the +,-
if ((current == '+' || current == '-') && lastOp != ' ' && lastOp != ')') {
if (current == '-') {
lastOp = ' '; // last is a number (not really necessary as digits are following an it's set there anyway)
sb.replace(pos, pos + 1, "-1 * "); // to make this another operation as probably asked from cg
//sb.insert(pos, " -1 * ");
pos += 5;
} else {
// a plus, just remove it
sb.replace(pos, pos + 1, "");
}
} else {
lastOp = current; // last is an operator
pos++;
sb.insert(pos++, ' ');
}
} else {
while (isDigit(current)) // as long as there are digits, advance
current = sb.charAt(++pos);
sb.insert(pos++, ' ');
lastOp = ' '; // last is a number
}
}
// System.out.println(sb);
// remove the end sentinel, split the stringbuilder to an array and return as list
return new LinkedList<>(Arrays.asList(sb.substring(0, sb.length() - 2).split("\\s+")));
}
public Solution() {
// Don't delete
}
}