Calculator with order of operations

Question

I am trying to make an additional option in my beginning calculator program, which is based on the BigDecimal class: the simultaneous solution for the entire operation by order of operations. I want to create methods by myself, however it took me a long time just to create a sketch, and for a moment I wonder if I chose a right way.

Right now, my only concern is the logic of this task, which I will implement in my program later. Does it make any sense to base such options, which will use a variety of number types, on a simple "looking for brackets" and operations on Strings? Does anyone see any flaws in that method?

import java.util.*;
public class OrderOfOperations {
 public static void main(String[] args){
 Scanner scanner = new Scanner(System.in);
 String s = scanner.nextLine();
 String w = result(s);
 System.out.println("Result: "+w);
 }
 public static String before(String s, int i){ //number before operation mark
 String str = s.substring(0,i);
 String num = "";
 for(int b=str.length()-1;b>=0;b--){
 if(b==0 || !Character.isDigit(str.charAt(b-1))&&str.charAt(b-1)!='.'){
 num=str.substring(b);
 break;
 }
 }
 return num;
 }
 public static String after(String s, int i){ //number after operation mark
 String str = s.substring(i+1);
 String num = "";
 for(int a=0;a<=str.length();a++){
 if(a==str.length() || !Character.isDigit(str.charAt(a))&&str.charAt(a)!='.'){
 num=str.substring(0,a);
 break;
 }
 }
 return num;
 }
 public static String result(String s){
 char o = '(';
 char c = ')';
 while(s.contains(Character.toString(o))||s.contains(Character.toString(c))){
 String in;
 if(s.contains(Character.toString(o))){
 System.out.println(s);
 in = s.substring(s.indexOf(o)+1);
 System.out.println("ino: "+in);
 s = s.substring(0, s.indexOf(o))+ result(in);
 }else if(s.contains(Character.toString(c))){
 in = s.substring(0, s.indexOf(c));
 System.out.println("inc: "+in);
 return count(in)+s.substring(s.indexOf(c)+1);
 }
 }
 return count(s);
 }
 public static String count(String s){
 String num1;
 double n1;
 String num2;
 double n2;
 for(int i=0; i<s.length();i++){
 if(s.charAt(i)=='*'||s.charAt(i)=='/'){
 num1 = before(s,i);
 System.out.println("nu1:" +num1);
 num2 = after(s,i);
 System.out.println("nu2:" +num2);
 n1 = Double.parseDouble(num1);
 n2 = Double.parseDouble(num2);
 double res = (s.charAt(i))=='*' ? n1*n2: n1/n2;
 s = s.substring(0,i-num1.length())+res+s.substring(i+num2.length()+1);
 i = 0;
 }
 }
 for(int i=0; i<s.length();i++){
 if(s.charAt(i)=='+'||s.charAt(i)=='-'){
 num1 = before(s,i);
 num2 = after(s,i);
 n1 = Double.parseDouble(num1);
 n2 = Double.parseDouble(num2);
 double res = (s.charAt(i))=='+' ? n1+n2: n1-n2;
 s = s.substring(0,i-num1.length())+res+s.substring(i+num2.length()+1);
 System.out.println("+:" + s);
 i=0;
 }
 }
 return s;
 }
}

Answer 1

Unfortunately, your algorithm is not correct. It evaluates an expression 1-(1+1)+1 to -2.0, but it is clear that the right answer is zero. It is not an implementation bug. The logic itself is wrong. So what can be done to avoid(or, at least, to minimize the risk of) ending up with an incorrect algorithm?

• You shouldn't make arbitrary assumptions. The algorithm you are using is not a well-known one, it is rather complex so it is not obvious whether it is correct or not, but you probably did not prove its correctness. For instance, you made an assumption that we can remove the first opening parenthesis and evaluate the part of the expression which goes after it separately. Is this assumption based on something? Did you try to figure out why it is correct? As you can see, it turned out to be incorrect. Proofs give you confidence in the logic of your solution.

• You can use already existing algorithms. Arithmetic expressions evaluation is a well-studied topic. There is an efficient shunting-yard algorithm, which runs in linear time and is proven to be correct. Reinventing a non-trivial algorithm is not a good idea(unless you deliberately decide to do it as an exercise, but in this case you should be able to reason about the correctness of your solution).

• Test your code in a systematic manner. Writing unit-tests is a good practice. The counterexample to your algorithm is rather short and simple, so you probably could have spotted that it is not correct if you had tested your code carefully.