5
\$\begingroup\$

Forget BIDMAS! Write a program that takes an equation and an operator precedence order, and prints the result.

Example input format:

1.2+3.4*5.6/7.8-9.0 */+-

Rules & guidelines:

  • The only operators that are defined are addition (+), subtraction (-), multiplication (*), and division (/). No parentheses, no exponentiation.
  • Associativity is always left-to-right. For example, 10/4/2 is to be interpreted as (10/4)/2 with a result of 1.25, rather than 10/(4/2).
  • The input format is as follows:
    • An equation, followed by a space, followed by the operator precedence specification (or two string arguments, one for the equation and the other for the precedence).
    • The equation comprises base-10 decimal numbers separated by operators, with no spaces. Integer values do not have to contain a period character, i.e. both 5 and 5.0 are to be accepted values.
    • For simplicity, negative numbers may not be included in the input, e.g. 6/3 is valid but 6/-3 is not. Input also may not contain a leading or trailing operator, so -6/3 isn't considered valid, nor is 6-3+.
    • The precedence specification string is always 4 characters long and always contains the characters +, -, /, and * once each. Precedence is read as left-to-right, e.g. */+- specifies multiplication with the highest precedence, division next, then addition, and finally subtraction. EDIT: It is acceptable to take the precedence string in reverse order (lowest to highest) as long as you specify this in your answer.
  • Input is a string to be taken via command line arguments, STDIN, or the default input format in programming languages that do not support these input methods.
  • You are free to assume that the given input will be in the correct format.
  • Output is via STDOUT or your language's normal output method.
  • The printed result should be in base-10 decimal.
  • Results must be computed to at least 4 decimal points of accuracy when compared to a correct implementation that uses double precision (64-bit) floating point arithmetic. This degree of freedom is designed to allow for the use of fixed-point arithmetic in languages that have no floating-point support.
  • Divide by zero, overflow, and underflow are undefined behaviour. Your code is free to assume that no inputs will be given that will trigger these cases.
  • You may not call out to any external services (e.g. Wolfram Alpha)
  • You may not call out to any programs whose primary function is to solve these types of problems.

Test cases:

  1. 6.3*7.8 followed by any operator precedence specification prints 49.14
  2. 2.2*3.3+9.9/8.8-1.1 */+- is parsed as ((2.2*3.3)+(9.9/8.8))-1.1 and should print 7.285
  3. 2.2*3.3+9.9/8.8-1.1 +*/- is parsed as ((2.2*(3.3+9.9))/8.8)-1.1 and should print 2.2
  4. 10/2+5-1 +-/* is parsed as 10/((2+5)-1) and the printed result should be 1.6666666...
  5. 2147480/90+10*5 +/-* is parsed as (2147480/(90+10))*5 and the printed result should be 107374
  6. 3*55-5/8/4+1 -/+* is parsed as 3*((((55-5)/8)/4)+1) should print 7.6875
  7. An input containing one thousand instances of the number 1.015 separated by multiplier operators (i.e. the expanded multiplicative form of 1.015^1000), followed by any operated precedence specification, should print a number within 0.0001 of 2924436.8604.

Code golf, so shortest code wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Related. \$\endgroup\$ – user202729 Nov 27 '17 at 15:14
  • 3
    \$\begingroup\$ Also related. \$\endgroup\$ – Arnauld Nov 27 '17 at 15:17
  • 3
    \$\begingroup\$ @Polynomial cough \$\endgroup\$ – NieDzejkob Nov 27 '17 at 15:34
  • 2
    \$\begingroup\$ @NieDzejkob In this case I think the input format is flexible enough, and HyperNeutrino's request to allow 5 arguments to a function as the expression removes a lot of the parsing work that makes this challenge interesting. Operator precedence in reverse order is acceptable, though, now that I think about it more. \$\endgroup\$ – Polynomial Nov 27 '17 at 15:47
  • 1
    \$\begingroup\$ @Polynomial I also think that five arguments is too much, but allowing two strings, one for the formula and one for the operators, seems reasonable. Splitting at white space is probably not the interesting part of parsing. \$\endgroup\$ – Laikoni Nov 27 '17 at 15:56

10 Answers 10

6
\$\begingroup\$

JavaScript (ES6), 94 bytes

Not particularly short, but fun. Adding parentheses all over the place...

s=>([e,o]=s.split` `,[...o].map(x=>e=e.split(x).join((a+=')')+x+(b+='(')),a=b=''),eval(b+e+a))

Test cases

let f =

s=>([e,o]=s.split` `,[...o].map(x=>e=e.split(x).join((a+=')')+x+(b+='(')),a=b=''),eval(b+e+a))

console.log(f("6.3*7.8 +-*/"))              // 49.14
console.log(f("2.2*3.3+9.9/8.8-1.1 */+-"))  // 7.285
console.log(f("2.2*3.3+9.9/8.8-1.1 +*/-"))  // 2.2
console.log(f("10/2+5-1 +-/*"))             // 1.6666
console.log(f("2147480/90+10*5 +/-*"))      // 107374
console.log(f("3*55-5/8/4+1 -/+*"))         // 7.6875

Historical note

A similar method was used in early FORTRAN compilers. Here is a link from archive.org to a relevant article written by Donald E. Knuth in a 1962 book called Computers and automation.

Examples

Let's consider the expression 2.2*3.3+9.9/8.8-1.1.

With operator precedence */+-, it will expand to:

((((2.2)*(3.3)))+(((9.9))/((8.8))))-((((1.1))))

With operator precedence +*/-, it will now expand to:

((((2.2))*((3.3)+(9.9)))/(((8.8))))-((((1.1))))

Removing all redundant parentheses, we get:

((2.2*3.3)+(9.9/8.8))-1.1 = 7.285

and:

((2.2*(3.3+9.9))/8.8)-1.1 = 2.2
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 174 133 bytes

Saved 41 bytes thanks to Arnauld.

i=>([e,o]=i.split` `,e=e.split(/([+*/-])/),[...o].map(x=>{while(~(b=e.indexOf(x)))e.splice(--b,3,eval(e.slice(b,b+3).join``))}),e[0])

First golf! This is probably terribly unoptimized.

Ungolfed:

f = input => {
    [equation, output] = input.split(" ");
    equation = equation.split(/([+*/-])/);
    [...output].map(x => {
        while (~(b = equation.indexOf(x))) {
            equation.splice(--b, 3, eval(equation.slice(b, b + 3).join("")));
        }
    });
    return equation[0];
};

This splits the input equation into tokens of numbers and operators, then iterates through operators in the specified order and collapses pairs of numbers using eval() until there's only one left.

JavaScript rounding error trash means that test case 3 results in 2.1999... instead of 2.2. I'm not sure if that disqualifies this answer, but oh well.

Test cases:

f=i=>([e,o]=i.split` `,e=e.split(/([+*/-])/),[...o].map(x=>{while(~(b=e.indexOf(x)))e.splice(--b,3,eval(e.slice(b,b+3).join``))}),e[0])

console.log(f("6.3*7.8 +-/*"));
console.log(f("2.2*3.3+9.9/8.8-1.1 */+-"));
console.log(f("2.2*3.3+9.9/8.8-1.1 +*/-"));
console.log(f("10/2+5-1 +-/*"));
console.log(f("2147480/90+10*5 +/-*"));
console.log(f("3*55-5/8/4+1 -/+*"));
console.log(f((new Array(1000)).fill("1.015").join("*") + " +-*/"));

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! Some quick wins: Use map instead of forEach. Use destructuring assignment [e,o]=i.split and then use e and o instead of a[0] and a[1]. \$\endgroup\$ – Arnauld Nov 27 '17 at 17:59
  • 1
    \$\begingroup\$ Welcome to PPCG, nice first solution. \$\endgroup\$ – Shaggy Nov 27 '17 at 18:30
  • 1
    \$\begingroup\$ You may also replace e.replace(/[+\-*/]/g," $& ").split` ` with e.split(/([+*/-])/) (splitting while capturing the separators). \$\endgroup\$ – Arnauld Nov 27 '17 at 21:13
  • \$\begingroup\$ @Arnauld Ooh, that's neat. Why does putting the character set in a capture group retain the separators? \$\endgroup\$ – Poyo Nov 27 '17 at 21:18
  • 1
    \$\begingroup\$ Quoting the specification: If separator is a regular expression that contains capturing parentheses, then each time separator is matched the results (including any undefined results) of the capturing parentheses are spliced into the output array. \$\endgroup\$ – Arnauld Nov 27 '17 at 21:22
3
\$\begingroup\$

JavaScript (ES6), 59 bytes

f=(s,[o,...a])=>eval(o?s.split(o).map(e=>f(e,a)).join(o):s)

Port of my golf of @HyperNeutrino's Python answer. Takes lowest precedence first.

\$\endgroup\$
  • \$\begingroup\$ ...wow, so much cleaner than my lousy attempt... \$\endgroup\$ – ETHproductions Nov 27 '17 at 23:21
  • \$\begingroup\$ that's amazing... \$\endgroup\$ – edc65 Nov 28 '17 at 6:56
  • \$\begingroup\$ @edc65 Oops, fixed! \$\endgroup\$ – Neil Nov 28 '17 at 8:48
2
\$\begingroup\$

Python 3, 77 bytes

f=lambda a,b:eval(b and b[0].join(str(f(A,b[1:]))for A in a.split(b[0]))or a)

Try it online!

-23 bytes thanks to Neil (takes operator precedence in reverse)
-1 byte thanks to Mr. Xcoder

\$\endgroup\$
  • 2
    \$\begingroup\$ 78 bytes: Try it online! \$\endgroup\$ – Neil Nov 27 '17 at 16:14
  • \$\begingroup\$ 77 bytes \$\endgroup\$ – Mr. Xcoder Nov 27 '17 at 17:53
  • \$\begingroup\$ @Mr.Xcoder thanks \$\endgroup\$ – HyperNeutrino Nov 27 '17 at 18:14
  • \$\begingroup\$ @edc65 pointed out in a comment on my answer that I forgot to make it clear that my golf takes the precedence string in reverse. \$\endgroup\$ – Neil Nov 28 '17 at 8:51
  • \$\begingroup\$ @Neil Ah yes, I didn't notice, thanks. I'll edit my answer to reflect that. \$\endgroup\$ – HyperNeutrino Nov 28 '17 at 12:58
1
\$\begingroup\$

Jelly, 21 bytes

ṣ⁹ḊṪ¤ñ€⁹Ṗ¤j⁹ḊṪ¤ŒVµ¹⁹?

Try it online!

Explanation

ṣ⁹ḊṪ¤ñ€⁹Ṗ¤j⁹ḊṪ¤ŒVµ¹⁹?  Main Link
                    ?  Ternary:
                   ⁹   If the right argument is truthy:
ṣ                      Split it by
  ḊṪ                   The last element of
 ⁹  ¤                  The right argument
      €                For each element
     ñ                 Call the next link as a dyad (wraps around so this calls the current link as a dyad)
       ⁹Ṗ¤             With right argument as `right_argument[:-1]`
          j            Join with
            ḊṪ         The last element of
           ⁹  ¤        The right argument
               ŒV      Evaluate as Python code
                 µ     Start a new monadic chain. If the right argument is falsy:
                  ¹    Identity: Return the left argument unmodified
\$\endgroup\$
  • \$\begingroup\$ Is this 21 bytes or 21 UTF-8 characters? Is Jelly one of those languages with a custom codepage to reduce things down to an 8-bit space? \$\endgroup\$ – Polynomial Dec 1 '17 at 12:45
  • \$\begingroup\$ @Polynomial Jelly is one of those languages. \$\endgroup\$ – HyperNeutrino Dec 1 '17 at 12:57
1
\$\begingroup\$

Proton, 87 bytes

x=>y=>eval((f=b=>a=>b?"(#{e.join(map(f(b[to-1]),a.split(e=b[-1])))})":a)(y)(x)).evalf()

Try it online!

+19 bytes to accommodate for the unnecessarily restrictive output format. seriously? the restriction is actually making the answers less accurate because now instead of precise fractional output it's giving inaccurate IEEE floating points... think about it...

\$\endgroup\$
  • \$\begingroup\$ Your "try it online" sample is outputting the result as a fraction rather than a decimal. \$\endgroup\$ – Polynomial Nov 27 '17 at 15:52
  • \$\begingroup\$ @Polynomial Does that really matter? If so, I can change it, but that's a feature of the language; making me change it would be considered cumbersome I/O format which is highly discouraged but up to you. \$\endgroup\$ – HyperNeutrino Nov 27 '17 at 16:02
  • \$\begingroup\$ I think normally it'd be a cumbersome I/O format in a different problem space, but in this case the question is specifically asking you to solve the numerical result of a formula, and outputting a different formula (which is what a fraction ultimately is) isn't really achieving that. Otherwise one could arguably just print the input for any case ^[0-9\.]+/[0-9\.]+$. \$\endgroup\$ – Polynomial Nov 27 '17 at 16:07
  • \$\begingroup\$ @Polynomial I disagree, a fraction is a numeric format, like a decimal expansion. A special case avoiding any work for the very special case a/b would be worthles for all others \$\endgroup\$ – edc65 Nov 27 '17 at 16:12
  • 1
    \$\begingroup\$ @Potato44 In the general case, yes, but since this challenge is explicitly about evaluating such expressions in the first place I do not agree that is an appropriate output format. If the decimal-only restriction takes the enjoyment out of the challenge for you, then I suggest just skipping this one. \$\endgroup\$ – Polynomial Nov 27 '17 at 19:12
1
\$\begingroup\$

Perl 5, 64 + 1 (-p) = 65 bytes

s/ .*//;for$i(map"\\$_",$&=~/./g){s/[\d.]*$i[0-9.]*/$&/ee&&redo}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 0-9 can be replaced with \d, however seems it's missing a loop to handle multiple instance of an operator for example 3*55-5/8/4+1 -/+* \$\endgroup\$ – Nahuel Fouilleul Nov 28 '17 at 13:58
  • \$\begingroup\$ You're right. It was only handling the first instance of each operator. \$\endgroup\$ – Xcali Nov 28 '17 at 14:21
  • \$\begingroup\$ \Q$i\E to avoid map"\\$_" \$\endgroup\$ – Nahuel Fouilleul Nov 28 '17 at 14:22
0
\$\begingroup\$

JavaScript (ES6), 96 bytes

f=(o,s)=>o?f(o.slice(s!=(s=s.replace(eval(['/','\\'+o[0],'/'].join`(\\d+\\.?\\d*)`),eval))),s):s

A non-recursive attempt was first made for this technique, but it came up at 101:

(s,o)=>[...o].map(x=>[...s].map(_=>s=s.replace(eval(['/','\\'+x,'/'].join`(\\d+\\.?\\d*)`),eval)))&&s
\$\endgroup\$
0
\$\begingroup\$

Clojure, 167 bytes

(defn f [i O](eval(read-string(or(first(filter some?(for[o O](let[[x y](clojure.string/split i(re-pattern(str \\ o))2)](when y(str" ("o\ (f x O)\ (f y O)")"))))))i))))

Whoa, long function names strike again! Operation precedence O is taken in "reverse" order.

\$\endgroup\$
0
\$\begingroup\$

C (gcc) , 276 bytes

A,B,u,i,j,k;double g(){double a,b,f[1000];char o[999],p[5];for(i=k=0;o[i++]^32&&scanf("%lf%c",&f[i],&o[i]););for(gets(p);k<4;k++)for(A=B=0;B<i;A=B){for(;!f[B++]&&i/B;);if(A&&o[--A]==p[k])u=p[k],a=f[A],b=f[--B],f[B]=u^42?u^43?u^45?a/b:a-b:a+b:a*b,f[A]=0,o[A]=o[B++];}a=f[i-1];}

Try it online

Slightly longer solution using NAN

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.