[Week Ten] Programming Contest- Basic Calculator

Welcome back to week ten of the weekly programming contests! If you are new to the contest or need a refresher don’t forget to read up on the rules and information Posted Here

WELCOME TO THE HOLDAY SPECIAL CHALLENGE!
I was going to do this last week but I couldn’t think of anything interesting

This weeks challenge is a little different, your job is to create a simple calculator class. The class must be named Calculator and have the public static method eval(String) which returns an integer. This class and method cannot be renamed. What the method should do is evaluate the given mathematical expression inputted as the String parameter and return the result of the expression. The calculator should support integers, arbitrary whitespace, addition, subtraction, negative numbers, and parentheses.

For this challenge, imports will count towards final character count, but static imports are allowed. ALL CHARACTERS WILL BE COUNTED

Examples:

calculate(“1 + 19 - 10”) -> 10
calculate(“1 - 14 - 10”) -> -23
calculate(“1 - (14 - 10)”) -> -3
calculate(“2 + 3”) -> 5
calculate("- 2 + 3 “) -> 1
calculate(”-3 - ( - 10 + 3) - 4") -> 0
calculate("(-3 - ( - 10 + 3)) - 4") -> 0

Please let me know if there are any issues with this challenge, there are a lot of moving parts and I’m not sure I covered them all.

Imports are allowed for this challenge but packages are limited to the following:

  • java.lang
  • java.util
  • comment if u want me to add something

Challenge Closes: Sunday 1/10/16

Good luck!

Couldn’t help myself

import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

public class Calculator {
    public static int eval(String input) {
        try {
            return (int) new ScriptEngineManager().getEngineByName("nashorn").eval(input);
        } catch (ScriptException e) {
            return 0;
        }
    }
}

No way would this be accepted right? :stuck_out_tongue:

1 Like

@simon816
You beat me to it… :frowning:
(that technically fits all the rules)

The only other way I’ve ever done this included ~10 classes…

Edit: In fact, you can see the way I did this here

2 Likes

Exactly what i meant by:

So no, i’m afraid that does not count :stuck_out_tongue: ive updated the rules


You really only have to implement positive and negative numbers. I tried to make it as simple as I could and still have it be mildly interesting

1 Like

Well I’ve written similar things in Python and PHP, time to do it in Java…
oh, and I did it using regex this one time

(?:(?P<var>[A-Za-z]+)|(?P<op>[\*+/\^]|-(?!\d))|(?P<num>(?:-)?(?:\d+\.\d+|\d+))|(?P<bracket>[\(\[]|[\)\]]))
2 Likes

Most blunt method, without using parsers, stacks, reverse Polish notation, etc. Just plain old FOR and recursion. It’s most big too, 488 characters :grin:.
Compressed:

public class Calculator{public static int eval(String u){int i=0,r=0,k;do{char c;String s="";boolean n=false,p=false;k=0;for(;i<u.length();i++){c=u.charAt(i);if((c==' '||c=='+')&&s=="")continue;if(p){if(c=='(')k++;if(c==')'){if(k==0){i++;break;}else k--;}s+=c;}else{if(c=='('){p=true;continue;}if(c=='-'&&s==""){n=!n;continue;}if(c>='0'&&c<='9')s+=c;else break;}}if(s==""&&i>=u.length())break;int t;if(p)t=eval(s);else t=Integer.parseInt(s);t*=n?-1:1;r+=t;}while(i<u.length());return r;}}

Full:

public class Calculator {
    public static int eval(String input) {
        int i = 0, result = 0, pn;
        do {
            char ch; String s = ""; boolean negative=false, p=false;
            pn=0;
            for (; i < input.length(); i++) {
                ch=input.charAt(i);
                if ((ch==' '||ch=='+') && s=="") continue;
                if (p) {
                    if (ch=='(') pn++;
                    if (ch==')')
                    {
                        if (pn==0) {i++; break;}
                        else pn--;
                    }
                    s+=ch;
                } else
                {
                    if (ch=='(') {p=true; continue;}
                    if (ch=='-' && s=="") { negative=!negative; continue;}
                    if (ch>='0' && ch<='9') s+=ch;
                    else break;
                }
            }
            if (s=="" && i >= input.length()) break;
            int tmp;
            if (p) tmp=eval(s);
            else tmp = Integer.parseInt(s);
            tmp *= negative ? -1 : 1;
            result+=tmp;
        } while (i < input.length());
        return result;
    }
}

P.S. Fixed.
P.P.S. It would be nice if first post examples include nested parentheses.

import java.util.regex.*;public class Calculator{public static int eval(String s){s=s.replace(" ","");s=s.replace("--","+");Matcher m=Pattern.compile("\\(([^(]*)\\)").matcher(s);if(m.find()){StringBuffer b =new StringBuffer();do m.appendReplacement(b, String.valueOf(eval(m.group(1))));while (m.find());m.appendTail(b);return eval(b.toString());}else{int n=1,r=0,h=0;for(char c: s.toCharArray())if("-+".indexOf(c)!=-1){r+=h*n;h=0;n=c=='-'?-1:1;}else h=h*10+c-'0';return r+h*n;}}}

479 characters

readable version

import java.util.regex.*;

public class Calculator {
    public static int eval(String s) {
        s = s.replace(" ", "");
        s = s.replace("--", "+");
        Matcher m = Pattern.compile("\\(([^(]*)\\)").matcher(s);
        if (m.find()) {
            StringBuffer b = new StringBuffer();
            do {
                m.appendReplacement(b, String.valueOf(eval(m.group(1))));
            } while (m.find());
            m.appendTail(b);
            return eval(b.toString());
        } else {
            int n = 1, r = 0, h = 0;
            for (char c : s.toCharArray()) {
                if ("-+".indexOf(c) != -1) {
                    r += h * n;
                    h = 0;
                    n = c == '-' ? -1 : 1;
                } else h = h * 10 + c - '0';
            }
            return r + h * n;
        }
    }
}

Using a recursive descent parser:

import java.util.*;

class Calculator {
    int eval(String s) {
        Queue<Character> l = new LinkedList<>();
        for (char c : s.toCharArray()) l.add(c);
        return parseAdd(l, parseSign(l));
    }

    int parseAdd(Queue<Character> l, int s) {
        parseWS(l);
        return !l.isEmpty() && "+-".indexOf(l.peek()) >= 0 ? parseAdd(l, s + (l.poll() == '+' ? 1 : -1) * parseSign(l)) : s;
    }

    int parseSign(Queue<Character> l) {
        parseWS(l);
        return ("+-".indexOf(l.peek()) >= 0 ? 44 - l.poll() : 1) * parseAtom(l);
    }

    int parseAtom(Queue<Character> l) {
        parseWS(l);
        if (l.peek() == '(') {
            l.poll(); int i = parseAdd(l, parseSign(l)); l.poll();
            return i;
        }
        return parseInt(l, 0);
    }

    int parseInt(Queue<Character> l, int p) {
        return !l.isEmpty() && Character.isDigit(l.peek()) ? parseInt(l, p * 10 + l.poll() - 48) : p;
    }

    void parseWS(Queue<Character> l) {
        if (!l.isEmpty() && Character.isWhitespace(l.peek())) {
            l.poll(); parseWS(l);
        }
    }
}

Compact version:

import java.util.*;class Calculator{int eval(String s){Queue<Character>l=new LinkedList<>();for(char c:s.toCharArray())l.add(c);return a(l,s(l));}int a(Queue<Character>l,int s){w(l);return!l.isEmpty()&&"+-".indexOf(l.peek())>=0?a(l,s+(l.poll()=='+'?1:-1)*s(l)):s;}int s(Queue<Character>l){w(l);return("+-".indexOf(l.peek())>=0?44-l.poll():1)*parseAtom(l);}int parseAtom(Queue<Character>l){w(l);if(l.peek()=='('){l.poll();int i=a(l,s(l));l.poll();return i;}return i(l,0);}int i(Queue<Character>l,int p){return!l.isEmpty()&&Character.isDigit(l.peek())?i(l,p*10+l.poll()-48):p;}void w(Queue<Character>l){if(!l.isEmpty()&&Character.isWhitespace(l.peek())){l.poll();w(l);}}}

669 characters.

The formal grammar I used:

ADD:    ADD ~ WS ~ P_CHAR ~ SIGN | SIGN
SIGN:   WS ~ P_CHAR ~ ATOM | ATOM
ATOM:   WS ~ '('ADD')' | WS ~ INT
INT:    INT ~ D_CHAR | D_CHAR

WS:     S_CHAR ~ WS | ''

P_CHAR: '+' | '-'
D_CHAR: `Character.isDigit(c)`
S_CHAR: `Character.isWhitespace(c)`

And a recursive parser that’s shorter than the regex parser by 4 characters - 475 characters:

public class Calculator{static int a[],b,c,o,p;public static int eval(String d){a=new int[(d+=")").length()];b=c=0;for(int e:d.toCharArray())if(e>32)a[c++]=e;return f();}static int f(){int g=n(),h;while((h=a[b++])>41)g=i(g,h);return g;}static int i(int j,int k){int l=n(),m=a[b];if((m==43|m>46)&k>42&k<46){b++;l=i(l,m);}if(k<43)return j*l;if(k<46)return j-l*(k-44);return j/l;}static int n() {if(a[b]<41){b++;return f();}o=0;for(;(p=a[b])>47&p<58;o=o*10+p-48)b++;return o;}}

Readable version (with usage of some ints replaced with chars, and some ASCII magic deciphered):

public class Calculator {
    // This is essentially a queue, but with shorter syntax.
    static char[] expression;
    static int index;

    public static int eval(String string) {
        // The input is evaluated as if it were in parentheses, so the parentheses method needs an ending parentheses.
        string += ")";

        // Copy the input into expression
        expression = new char[string.length()];
        index = 0;
        int writeIndex = 0;
        for (char character : string.toCharArray()) {
            if (!Character.isWhitespace(character)) { // Shortened to character < 32
                expression[writeIndex++] = character;
            }
        }

        // And evaluate it.
        return parseParentheses();
    }

    static int parseParentheses() {
        int first = parseNumber();
        char operator;
        while ((operator = expression[index++]) != ')') { // Shortened to (operator = expression[index++]) > 41
            first = applyOperator(first, operator);
        }
        return first;
    }

    static int applyOperator(int firstArg, char operator) {
        // This is where precedence is applied.
        int secondArg = parseNumber();
        char nextOperator = expression[index];
        // Shortened to (nextOperator == 43 | nextOperator > 46) & operator > 42 & operator < 46
        if ((nextOperator == '*' || nextOperator == '/') && (operator == '+' || operator == '-')) {
            index++;
            secondArg = applyOperator(secondArg, nextOperator);
        }

        // And this is where the actual operations occur. Order was set based on the order of the character points.
        if (operator == '*') { // Shortened to operator < 43
            return firstArg * secondArg;
        }
        if (operator == '+' || operator == '-') { // Shortened to operator < 46
            // ASCII magic - '+' == 44, and '-' == 46.
            return firstArg - secondArg * (operator - 44);
        }
        return firstArg / secondArg;
    }

    static int parseNumber() {
        if (expression[index] == '(') { // Shortened to expression[index] < 41
            index++;
            return parseParentheses();
        }
        int num = 0;
        // Loop shortened to for (int p; (p = expression[index]) > 47 & p < 58; num = num * 10 + p - 48) index++;
        while (expression[index] > 47 && expression[index] < 58) {
            // expression[index] - '0' basically parses an ASCII digit into its numeric form.
            num = num * 10 + expression[index] - '0';
            index++;
        }
        return num;
    }
}

And just for fun, here’s a JavaScript version:

(JavaScript already defines an eval() function which satisfies the challenge. :wink:)

Added an example

294 character

public class Calculator{public static int eval(String s){int n=1,r=0,h=0,p,q,c,i=0;for(;i<s.length();i++)if((c=s.charAt(i))>32)if(c<41){q=i;p=1;while((p+=(c=s.charAt(++i))==40?1:c==41?-1:0)>0);r+=eval(s.substring(q+1,i))*n;}else if(c<48){r+=h*n;h=0;n=c>44?-1:1;}else h=h*10+c-48;return r+h*n;}}

semi-readable version

public class Calculator {
    public static int eval(String s) {
        int n = 1, r = 0, h = 0, p, q, c, i = 0;
        for (; i < s.length(); i++)
            if ((c = s.charAt(i)) > 32) if (c < 41) {
                q = i;
                p = 1;
                while ((p += (c = s.charAt(++i)) == 40 ? 1 : c == 41 ? -1 : 0) > 0) ;
                r += eval(s.substring(q + 1, i)) * n;
            } else if (c < 48) {
                r += h * n;
                h = 0;
                n = c > 44 ? -1 : 1;
            } else h = h * 10 + c - 48;
        return r + h * n;
    }
}
2 Likes

Congratulations to @CodeCrafter47 for winning week ten!

The next weeks challenge will be up shortly