Code Golf: Mathematical expression evaluator (that respects PEMDAS)
https://stackoverflow.com/questions/1384811
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
I challenge you to write a mathematical expression evaluator that respects PEMDAS (order of operations: parentheses, exponentiation, multiplication, division, addition, subtraction) without using regular expressions, a pre-existing "Eval()"-like function, a parsing library, etc.
I saw one pre-existing evaluator challenge on SO (here), but that one specifically required left-to-right evaluation.
Sample inputs and outputs:
"-1^(-3*4/-6)" -> "1"
"-2^(2^(4-1))" -> "256"
"2*6/4^2*4/3" -> "1"
I wrote an evaluator in C#, but would like to see how badly it compares to those of smarter programmers in their languages of choice.
Related:
Clarifications:
Let's make this a function that accepts a string argument and returns a string result.
As for why no regexes, well, that's to level the playing field. I think there ought to be a separate challenge for "the most compact regex".
Using StrToFloat() is acceptable. By "parsing library" I meant to exclude such things as general-purpose grammar parsers, also to level the playing-field.
Support floats.
Support paretheses, exponentiation, and the four arithmetic operators.
Give multiplication and division equal precedence.
Give addition and subtraction equal precedence.
For simplicity, you may assume all inputs are well-formed.
I don't have a preference as to whether your function accepts such things as ".1" or "1e3" as valid numbers, but accepting them would earn you brownie points. ;)
For divide-by-zero cases, you could perhaps return "NaN" (assuming you wish to implement error handling).
Solution
C (465 characters)
#define F for(i=0;P-8;i+=2)
#define V t[i
#define P V+1]
#define S V+2]),K(&L,4),i-=2)
#define L V-2]
K(double*t,int i){for(*++t=4;*t-8;*++t=V])*++t=V];}M(double*t){int i,p,b;
F if(!P)for(p=1,b=i;i+=2,p;)P?P-1||--p||(P=8,M(t+b+2),K(t+b,i-b),i=b):++p;
F P-6||(L=pow(L,S;F P-2&&P-7||(L*=(P-7?V+2]:1/S;F P-4&&(L+=(P-5?V+2]:-S;
F L=V];}E(char*s,char*r){double t[99];char*e,i=2,z=0;for(;*s;i+=2)V]=
strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;P=8;M(t+2);sprintf(r,"%g",*t);}
The first five newlines are required, the rest are there just for readability. I've counted the first five newlines as one character each. If you want to measure it in lines, it was 28 lines before I removed all the whitespace, but that's a pretty meaningless number. It could have been anything from 6 lines to a million, depending on how I formatted it.
The entry point is E() (for "evaluate"). The first parameter is the input string, and the second parameter points to the output string, and must be allocated by the caller (as per usual C standards). It can handle up to 47 tokens, where a token is either an operator (one of "+-*/^()"), or a floating point number. Unary sign operators do not count as a separate token.
This code is loosely based on a project I did many years ago as an exercise. I took out all the error handling and whitespace skipping and retooled it using golf techniques. Below are the 28 lines, with enough formatting that I was able to write it, but probably not enough to read it. You'll want to #include <stdlib.h>, <stdio.h>, and <math.h> (or see note at the bottom).
See after the code for an explanation of how it works.
#define F for(i=0;P-8;i+=2)
#define V t[i
#define P V+1]
#define S V+2]),K(&L,4),i-=2)
#define L V-2]
K(double*t,int i){
for(*++t=4;*t-8;*++t=V])
*++t=V];
}
M(double*t){
int i,p,b;
F if(!P)
for(p=1,b=i;i+=2,p;)
P?P-1||--p||(P=8,M(t+b+2),K(t+b,i-b),i=b):++p;
F P-6||(L=pow(L,S;
F P-2&&P-7||(L*=(P-7?V+2]:1/S;
F P-4&&(L+=(P-5?V+2]:-S;
F L=V];
}
E(char*s,char*r){
double t[99];
char*e,i=2,z=0;
for(;*s;i+=2)
V]=strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;
P=8;
M(t+2);
sprintf(r,"%g",*t);
}
The first step is to tokenize. The array of doubles contains two values for each token, an operator (P, because O looks too much like zero), and a value (V). This tokenizing is what is done in the for loop in E(). It also deals with any unary + and - operators, incorporating them into the constant.
The "operator" field of the token array can have one of the following values:
0:
(
1:)
2:*
3:+
4: a floating-point constant value
5:-
6:^
7:/
8: end of token string
This scheme was largely derived by Daniel Martin, who noticed that the last 3 bits were unique in the ASCII representation of each of the operators in this challenge.
An uncompressed version of E() would look something like this:
void Evaluate(char *expression, char *result){
double tokenList[99];
char *parseEnd;
int i = 2, prevOperator = 0;
/* i must start at 2, because the EvalTokens will write before the
* beginning of the array. This is to allow overwriting an opening
* parenthesis with the value of the subexpression. */
for(; *expression != 0; i += 2){
/* try to parse a constant floating-point value */
tokenList[i] = strtod(expression, &parseEnd);
/* explanation below code */
if(parseEnd != expression && prevOperator != 4/*constant*/ &&
prevOperator != 1/*close paren*/){
expression = parseEnd;
prevOperator = tokenList[i + 1] = 4/*constant*/;
}else{
/* it's an operator */
prevOperator = tokenList[i + 1] = *expression & 7;
expression++;
}
}
/* done parsing, add end-of-token-string operator */
tokenList[i + 1] = 8/*end*/
/* Evaluate the expression in the token list */
EvalTokens(tokenList + 2); /* remember the offset by 2 above? */
sprintf(result, "%g", tokenList[0]/* result ends up in first value */);
}
Since we're guaranteed valid input, the only reason the parsing would fail would be because the next token is an operator. If this happens, the parseEnd pointer will be the same as, tokenStart. We must also handle the case where parsing succeeded, but what we really wanted was an operator. This would occur for the addition and subtraction operators, unless a sign operator directly followed. In other words, given the expression "4-6", we want to parse it as {4, -, 6}, and not as {4, -6}. On the other hand, given "4+-6", we should parse it as {4, +, -6}. The solution is quite simple. If parsing fails OR the preceding token was a constant or a closing parenthesis (effectively a subexpression which will evaluate to a constant), then the current token is an operator, otherwise it's a constant.
After tokenizing is done, calculating and folding are done by calling M(), which first looks for any matched pairs of parentheses and processes the subexpressions contained within by calling itself recursively. Then it processes operators, first exponentiation, then multiplication and division together, and finally addition and subtraction together. Because well-formed input is expected (as specified in the challenge), it doesn't check for the addition operator explicitly, since it's the last legal operator after all the others are processed.
The calculation function, lacking golf compression, would look something like this:
void EvalTokens(double *tokenList){
int i, parenLevel, parenStart;
for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
if(tokenList[i + 1] == 0/*open paren*/)
for(parenLevel = 1, parenStart = i; i += 2, parenLevel > 0){
if(tokenList[i + 1] == 0/*another open paren*/)
parenLevel++;
else if(tokenList[i + 1] == 1/*close paren*/)
if(--parenLevel == 0){
/* make this a temporary end of list */
tokenList[i + 1] = 8;
/* recursively handle the subexpression */
EvalTokens(tokenList + parenStart + 2);
/* fold the subexpression out */
FoldTokens(tokenList + parenStart, i - parenStart);
/* bring i back to where the folded value of the
* subexpression is now */
i = parenStart;
}
}
for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
if(tokenList[i + 1] == 6/*exponentiation operator (^)*/){
tokenList[i - 2] = pow(tokenList[i - 2], tokenList[i + 2]);
FoldTokens(tokenList + i - 2, 4);
i -= 2;
}
for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
if(tokenList[i + 1] == 2/*multiplication operator (*)*/ ||
tokenList[i + 1] == 7/*division operator (/)*/){
tokenList[i - 2] *=
(tokenList[i + 1] == 2 ?
tokenList[i + 2] :
1 / tokenList[i + 2]);
FoldTokens(tokenList + i - 2, 4);
i -= 2;
}
for(i = 0; tokenList[i + 1] != 8/*end*/; i+= 2)
if(tokenList[i + 1] != 4/*constant*/){
tokenList[i - 2] +=
(tokenList[i + 1] == 3 ?
tokenList[i + 2] :
-tokenList[i + 2]);
FoldTokens(tokenList + i - 2, 4);
i -= 2;
}
tokenList[-2] = tokenList[0];
/* the compressed code does the above in a loop, equivalent to:
*
* for(i = 0; tokenList[i + 1] != 8; i+= 2)
* tokenList[i - 2] = tokenList[i];
*
* This loop will actually only iterate once, and thanks to the
* liberal use of macros, is shorter. */
}
Some amount of compression would probably make this function easier to read.
Once an operation is performed, the operands and operator are folded out of the token list by K() (called through the macro S). The result of the operation is left as a constant in place of the folded expression. Consequently, the final result is left at the beginning of the token array, so when control returns to E(), it simply prints that to a string, taking advantage of the fact that the first value in the array is the value field of the token.
This call to FoldTokens() takes place either after an operation (^, *, /, +, or -) has been performed, or after a subexpression (surrounded by parentheses) has been processed. The FoldTokens() routine ensures that the result value has the correct operator type (4), and then copies the rest of the larger expression of the subexpression. For instance, when the expression "2+6*4+1" is processed, EvalTokens() first calculates 6*4, leaving the result in place of the 6 (2+24*4+1). FoldTokens() then removes the rest of the sub expression "24*4", leaving 2+24+1.
void FoldTokens(double *tokenList, int offset){
tokenList++;
tokenList[0] = 4; // force value to constant
while(tokenList[0] != 8/*end of token string*/){
tokenList[0] = tokenList[offset];
tokenList[1] = tokenList[offset + 1];
tokenList += 2;
}
}
That's it. The macros are just there to replace common operations, and everything else is just golf-compression of the above.
strager insists that the code should include #include statements, as it will not function correctly without a proper forward declation of the strtod and pow and functions. Since the challenge asks for just a function, and not a complete program, I hold that this should not be required. However, forward declarations could be added at minimal cost by adding the following code:
#define D double
D strtod(),pow();
I would then replace all instances of "double" in the code with "D". This would add 19 characters to the code, bringing the total up to 484. On the other hand, I could also convert my function to return a double instead of a string, as did he, which would trim 15 characters, changing the E() function to this:
D E(char*s){
D t[99];
char*e,i=2,z=0;
for(;*s;i+=2)
V]=strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;
P=8;
M(t+2);
return*t;
}
This would make the total code size 469 characters (or 452 without the forward declarations of strtod and pow, but with the D macro). It would even be possible to trim 1 more characters by requiring the caller to pass in a pointer to a double for the return value:
E(char*s,D*r){
D t[99];
char*e,i=2,z=0;
for(;*s;i+=2)
V=strtod(s,&e),P=z=e-s&&z-4&&z-1?s=e,4:*s++&7;
P=8;
M(t+2);
*r=*t;
}
I'll leave it to the reader to decide which version is appropriate.
OTHER TIPS
C#, 13 lines:
static string Calc(string exp)
{
WebRequest request = WebRequest.Create("http://google.com/search?q=" +
HttpUtility.UrlDecode(exp));
using (WebResponse response = request.GetResponse())
using (Stream dataStream = response.GetResponseStream())
using (StreamReader reader = new StreamReader(dataStream))
{
string r = reader.ReadToEnd();
int start = r.IndexOf(" = ") + 3;
int end = r.IndexOf("<", start);
return r.Substring(start, end - start);
}
}
This compresses down to about 317 characters:
static string C(string e){var q = WebRequest.Create("http://google.com/search?q="
+HttpUtility.UrlDecode(e));using (var p=q.GetResponse()) using (var s=
p.GetResponseStream()) using (var d = new StreamReader(dataStream)){var
r=d.ReadToEnd();var t=r.IndexOf(" = ") + 3;var e=r.IndexOf("<",t);return
r.Substring(t,e-t);}}
Thanks to Mark and P Daddy in the comments, is compresses to 195 characters:
string C(string f){using(var c=new WebClient()){var r=c.DownloadString
("http://google.com/search?q="+HttpUtility.UrlDecode(f));int s=r.IndexOf(
" = ")+3;return r.Substring(s,r.IndexOf("<",f)-s);}}
J
:[[/%^(:[[+-/^,&i|:[$[' ']^j+0__:k<3:]]
F#, 70 lines
Ok, I implement a monadic parser combinator library, and then use that library to solve this problem. All told it's still just 70 lines of readable code.
I assume exponentiation associates to the right, and the other operators associate to the left. Everything works on floats (System.Doubles). I did not do any error handling for bad inputs or divide-by-zero.
// Core Parser Library
open System
let Fail() = fun i -> None
type ParseMonad() =
member p.Return x = fun i -> Some(x,i)
member p.Bind(m,f) = fun i ->
match m i with
| Some(x,i2) -> f x i2
| None -> None
let parse = ParseMonad()
let (<|>) p1 p2 = fun i ->
match p1 i with
| Some r -> Some(r)
| None -> p2 i
let Sat pred = fun i ->
match i with
| [] -> None
| c::cs -> if pred c then Some(c, cs) else None
// Auxiliary Parser Library
let Digit = Sat Char.IsDigit
let Lit (c : char) r =
parse { let! _ = Sat ((=) c)
return r }
let Opt p = p <|> parse { return [] }
let rec Many p = Opt (Many1 p)
and Many1 p = parse { let! x = p
let! xs = Many p
return x :: xs }
let Num = parse {
let! sign = Opt(Lit '-' ['-'])
let! beforeDec = Many Digit
let! rest = parse { let! dec = Lit '.' '.'
let! afterDec = Many Digit
return dec :: afterDec } |> Opt
let s = new string(List.concat([sign;beforeDec;rest])
|> List.to_array)
match(try Some(float s) with e -> None)with
| Some(r) -> return r
| None -> return! Fail() }
let Chainl1 p op =
let rec Help x = parse { let! f = op
let! y = p
return! Help (f x y) }
<|> parse { return x }
parse { let! x = p
return! Help x }
let rec Chainr1 p op =
parse { let! x = p
return! parse { let! f = op
let! y = Chainr1 p op
return f x y }
<|> parse { return x } }
// Expression grammar of this code-golf question
let AddOp = Lit '+' (fun x y -> 0. + x + y)
<|> Lit '-' (fun x y -> 0. + x - y)
let MulOp = Lit '*' (fun x y -> 0. + x * y)
<|> Lit '/' (fun x y -> 0. + x / y)
let ExpOp = Lit '^' (fun x y -> Math.Pow(x,y))
let rec Expr = Chainl1 Term AddOp
and Term = Chainl1 Factor MulOp
and Factor = Chainr1 Part ExpOp
and Part = Num <|> Paren
and Paren = parse { do! Lit '(' ()
let! e = Expr
do! Lit ')' ()
return e }
let CodeGolf (s:string) =
match Expr(Seq.to_list(s.ToCharArray())) with
| None -> "bad input"
| Some(r,_) -> r.ToString()
// Examples
printfn "%s" (CodeGolf "1.1+2.2+10^2^3") // 100000003.3
printfn "%s" (CodeGolf "10+3.14/2") // 11.57
printfn "%s" (CodeGolf "(10+3.14)/2") // 6.57
printfn "%s" (CodeGolf "-1^(-3*4/-6)") // 1
printfn "%s" (CodeGolf "-2^(2^(4-1))") // 256
printfn "%s" (CodeGolf "2*6/4^2*4/3") // 1
The parser representation type is
type P<'a> = char list -> option<'a * char list>
by the way, a common one for non-error-handling parsers.
Recursive descent parser in PARLANSE, a C-like langauge with LISP syntax: [70 lines, 1376 characters not counting indent-by-4 needed by SO] EDIT: Rules changed, somebody insisted on floating point numbers, fixed. No library calls except the float conversion, input and print. [now 94 lines, 1825 characters]
(define main (procedure void)
(local
(;; (define f (function float void))
(= [s string] (append (input) "$"))
(= [i natural] 1)
(define S (lambda f
(let (= v (P))
(value (loop
(case s:i)
"+" (;; (+= i) (+= v (P) );;
"-" (;; (+= i) (-= v (P) );;
else (return v)
)case
)loop
v
)value
)define
(define P (lambda f
(let (= v (T))
(value (loop
(case s:i)
"*" (;; (+= i) (= v (* v (T)) );;
"/" (;; (+= i) (= v (/ v (T)) );;
else (return v)
)case
)loop
v
)value
)define
(define T (lambda f
(let (= v (O))
(value (loop
(case s:i)
"^" (;; (+= i) (= v (** v (T)) );;
else (return v)
)case
)loop
v
)value
)define
(define O (lambda f
(let (= v +0)
(value
(case s:i)
"(" (;; (+= i) (= v (E)) (+= i) );;
"-" (;; (+= i) (= v (- 0.0 (O))) );;
else (= v (StringToFloat (F))
)value
v
)let
)define
(define F (lambda f)
(let (= n (N))
(value
(;; (ifthen (== s:i ".")
(;; (+= i)
(= n (append n "."))
(= n (concatenate n (N)))
);;
)ifthen
(ifthen (== s:i "E")
(;; (+= i)
(= n (append n "E"))
(ifthen (== s:i "-")
(;; (+= i)
(= n (append n "-"))
(= n (concatenate n (N)))
);;
);;
)ifthen
);;
n
)let
)define
(define N (lambda (function string string)
(case s:i
(any "0" "1" "2" "3" "4" "5" "6" "7" "8" "9")
(value (+= i)
(append ? s:(-- i))
)value
else ?
)case
)define
);;
(print (S))
)local
)define
Assumes a well-formed expression, float numbers with at least one leading digit, exponents optional as Enn or E-nnn. Not compiled and run.
Pecularities: the definition f is essentially signature typedef. The lambdas are the parsing functions, one per grammar rule. A function F is called by writing (F args). PARLANSE functions are lexically scoped, so each function has implicit access to the expression s to be evaluated and a string scanning index i.
The grammar implemented is:
E = S $ ;
S = P ;
S = S + P ;
P = T ;
P = P * T ;
T = O ;
T = O ^ T ;
O = ( S ) ;
O = - O ;
O = F ;
F = digits {. digits} { E {-} digits} ;
F#, 589 chars
I golf-compressed my prior solution into this gem:
let rec D a=function|c::s when System.Char.IsDigit c->D(c::a)s|s->a,s
and L p o s=
let rec K(a,s)=match o s with|None->a,s|Some(o,t)->let q,t=p t in K(o a q,t)
K(p s)
and E=L(L F (function|'*'::s->Some((*),s)|'/'::s->Some((/),s)|_->None))(
function|'+'::s->Some((+),s)|'-'::s->Some((-),s)|_->None)
and F s=match P s with|x,'^'::s->let y,s=F s in x**y,s|r->r
and P=function|'('::s->let r,_::s=E s in r,s|s->(
let a,s=match(match s with|'-'::t->D['-']t|_->D[]s)with|a,'.'::t->D('.'::a)t|r->r
float(new string(Seq.to_array(List.rev a))),s)
and G s=string(fst(E(Seq.to_list s)))
Tests:
printfn "%s" (G "1.1+2.2+10^2^3") // 100000003.3
printfn "%s" (G "10+3.14/2") // 11.57
printfn "%s" (G "(10+3.14)/2") // 6.57
printfn "%s" (G "-1^(-3*4/-6)") // 1
printfn "%s" (G "-2^(2^(4-1))") // 256
printfn "%s" (G "2*6/4^2*4/3") // 1
printfn "%s" (G "3-2-1") // 0
C# (with much LINQ), 150 lines
Ok, I implement a monadic parser combinator library, and then use that library to solve this problem. All told it's about 150 lines of code. (This is basically a straight transliteration of my F# solution.)
I assume exponentiation associates to the right, and the other operators associate to the left. Everything works on System.Doubles. I did not do any error handling for bad inputs or divide-by-zero.
using System;
using System.Collections.Generic;
using System.Linq;
class Option<T>
{
public T Value { get; set; }
public Option(T x) { Value = x; }
}
delegate Option<KeyValuePair<T,List<char>>> P<T>(List<char> input);
static class Program
{
static List<T> Cons<T>(T x, List<T> xs)
{
var r = new List<T>(xs);
r.Insert(0, x);
return r;
}
static Option<T> Some<T>(T x) { return new Option<T>(x); }
static KeyValuePair<T,List<char>> KVP<T>(T x, List<char> y)
{ return new KeyValuePair<T,List<char>>(x,y); }
// Core Parser Library
static P<T> Fail<T>() { return i => null; }
static P<U> Select<T, U>(this P<T> p, Func<T, U> f)
{
return i =>
{
var r = p(i);
if (r == null) return null;
return Some(KVP(f(r.Value.Key),(r.Value.Value)));
};
}
public static P<V> SelectMany<T, U, V>(this P<T> p, Func<T, P<U>> sel, Func<T, U, V> prj)
{
return i =>
{
var r = p(i);
if (r == null) return null;
var p2 = sel(r.Value.Key);
var r2 = p2(r.Value.Value);
if (r2 == null) return null;
return Some(KVP(prj(r.Value.Key, r2.Value.Key),(r2.Value.Value)));
};
}
static P<T> Or<T>(this P<T> p1, P<T> p2)
{
return i =>
{
var r = p1(i);
if (r == null) return p2(i);
return r;
};
}
static P<char> Sat(Func<char,bool> pred)
{
return i =>
{
if (i.Count == 0 || !pred(i[0])) return null;
var rest = new List<char>(i);
rest.RemoveAt(0);
return Some(KVP(i[0], rest));
};
}
static P<T> Return<T>(T x)
{
return i => Some(KVP(x,i));
}
// Auxiliary Parser Library
static P<char> Digit = Sat(Char.IsDigit);
static P<T> Lit<T>(char c, T r)
{
return from dummy in Sat(x => x == c)
select r;
}
static P<List<T>> Opt<T>(P<List<T>> p)
{
return p.Or(Return(new List<T>()));
}
static P<List<T>> Many<T>(P<T> p)
{
return Many1<T>(p).Or(Return(new List<T>()));
}
static P<List<T>> Many1<T>(P<T> p)
{
return from x in p
from xs in Many(p)
select Cons(x, xs);
}
static P<T> Chainl1<T>(this P<T> p, P<Func<T, T, T>> op)
{
return from x in p
from r in Chainl1Helper(x, p, op)
select r;
}
static P<T> Chainl1Helper<T>(T x, P<T> p, P<Func<T, T, T>> op)
{
return (from f in op
from y in p
from r in Chainl1Helper(f(x, y), p, op)
select r)
.Or(Return(x));
}
static P<T> Chainr1<T>(this P<T> p, P<Func<T, T, T>> op)
{
return (from x in p
from r in (from f in op
from y in Chainr1(p, op)
select f(x, y))
.Or(Return(x))
select r);
}
static P<double> TryParse(string s)
{
double d;
if (Double.TryParse(s, out d)) return Return(d);
return Fail<double>();
}
static void Main(string[] args)
{
var Num = from sign in Opt(Lit('-', new List<char>(new []{'-'})))
from beforeDec in Many(Digit)
from rest in Opt(from dec in Lit('.','.')
from afterDec in Many(Digit)
select Cons(dec, afterDec))
let s = new string(Enumerable.Concat(sign,
Enumerable.Concat(beforeDec, rest))
.ToArray())
from r in TryParse(s)
select r;
// Expression grammar of this code-golf question
var AddOp = Lit('+', new Func<double,double,double>((x,y) => x + y))
.Or(Lit('-', new Func<double, double, double>((x, y) => x - y)));
var MulOp = Lit('*', new Func<double, double, double>((x, y) => x * y))
.Or(Lit('/', new Func<double, double, double>((x, y) => x / y)));
var ExpOp = Lit('^', new Func<double, double, double>((x, y) => Math.Pow(x, y)));
P<double> Expr = null;
P<double> Term = null;
P<double> Factor = null;
P<double> Part = null;
P<double> Paren = from _1 in Lit('(', 0)
from e in Expr
from _2 in Lit(')', 0)
select e;
Part = Num.Or(Paren);
Factor = Chainr1(Part, ExpOp);
Term = Chainl1(Factor, MulOp);
Expr = Chainl1(Term, AddOp);
Func<string,string> CodeGolf = s =>
Expr(new List<char>(s)).Value.Key.ToString();
// Examples
Console.WriteLine(CodeGolf("1.1+2.2+10^2^3")); // 100000003.3
Console.WriteLine(CodeGolf("10+3.14/2")); // 11.57
Console.WriteLine(CodeGolf("(10+3.14)/2")); // 6.57
Console.WriteLine(CodeGolf("-1^(-3*4/-6)")); // 1
Console.WriteLine(CodeGolf("-2^(2^(4-1))")); // 256
Console.WriteLine(CodeGolf("2*6/4^2*4/3")); // 1
}
}
C99 (565 characters)
Minified
#include<stdio.h>
#include<string.h>
#include<math.h>
float X(char*c){struct{float f;int d,c;}N[99],*C,*E,*P;char*o="+-*/^()",*q,d=1,x
=0;for(C=N;*c;){C->f=C->c=0;if(q=strchr(o,*c)){if(*c<42)d+=*c-41?8:-8;else{if(C
==N|C[-1].c)goto F;C->d=d+(q-o)/2*2;C->c=q-o+1;++C;}++c;}else{int n=0;F:sscanf(c
,"%f%n",&C->f,&n);c+=n;C->d=d;++C;}}for(E=N;E-C;++E)x=E->d>x?E->d:x;for(;x>0;--x
)for(E=P=N;E-C;E->d&&!E->c?P=E:0,++E)if(E->d==x&&E->c){switch((E++)->c){
#define Z(x,n)case n:P->f=P->f x E->f;break;
Z(+,1)Z(-,2)Z(*,3)Z(/,4)case 5:P->f=powf(P->f,E->f);}E->d=0;}return N->f;}
Expanded
#include<stdio.h>
#include<string.h>
#include<math.h>
float X(char*c){
struct{
float f;
int d,c;
}N[99],*C,*E,*P;
char*o="+-*/^()",*q,d=1,x=0;
for(C=N;*c;){
C->f=C->c=0;
if(q=strchr(o,*c)){
if(*c<42) // Parentheses.
d+=*c-41?8:-8;
else{ // +-*/^.
if(C==N|C[-1].c)
goto F;
C->d=d+(q-o)/2*2;
C->c=q-o+1;
++C;
}
++c;
}else{
int n=0;
F:
sscanf(c,"%f%n",&C->f,&n);
c+=n;
C->d=d;
++C;
}
}
for(E=N;E-C;++E)
x=E->d>x?E->d:x;
for(;x>0;--x)
for(E=P=N;E-C;E->d&&!E->c?P=E:0,++E)
if(E->d==x&&E->c){
switch((E++)->c){
#define Z(x,n)case n:P->f=P->f x E->f;break;
Z(+,1)
Z(-,2)
Z(*,3)
Z(/,4)
case 5:
P->f=powf(P->f,E->f);
}
E->d=0;
}
return N->f;
}
int main(){
assert(X("2+2")==4);
assert(X("-1^(-3*4/-6)")==1);
assert(X("-2^(2^(4-1))")==256);
assert(X("2*6/4^2*4/3")==1);
puts("success");
}
Explanation
Developed my own technique. Figure it out yourself. =]
C (277 characters)
#define V(c)D o;for(**s-40?*r=strtod(*s,s):(++*s,M(s,r)),o=**s?strchr(t,*(*s)++)-t:0;c;)L(r,&o,s);
typedef char*S;typedef double D;D strtod(),pow();S*t=")+-*/^",strchr();
L(D*v,D*p,S*s){D u,*r=&u;V(*p<o)*v=*p-1?*p-2?*p-3?*p-4?pow(*v,u):*v/u:
*v*u:*v-u:*v+u;*p=o;}M(S*s,D*r){V(o)}
The first newline is required, and I've counted it as one character.
This is a completely different approach from my other answer. It's more of a functional approach. Instead of tokenizing and looping through several times, this one evaluates the expression in one pass, using recursive calls for higher-precedence operators, effectively using the call stack to store state.
To satisfy strager ;), this time I've included forward declarations of strtod(), pow(), and strchr(). Taking them out would save 26 characters.
The entry point is M(). The input string is the first parameter, and the output double is the second parameter. The entry point used to be E(), which returned a string, as the OP asked. But since mine was the only C implementation doing so, I decided to yank it out (peer pressure, and all). Adding it back in would add 43 characters:
E(S s,S r){D v;M(&s,&v);sprintf(r,"%g",v);}
Below is the code before I compressed it:
double strtod(),pow(),Solve();
int OpOrder(char op){
int i=-1;
while("\0)+-*/^"[++i] != op);
return i/2;
}
double GetValue(char **s){
if(**s == '('){
++*s;
return Solve(s);
}
return strtod(*s, s);
}
double Calculate(double left, char *op, char **s){
double right;
char rightOp;
if(*op == 0 || *op == ')')
return left;
right = GetValue(s);
rightOp = *(*s)++;
while(OpOrder(*op) < OpOrder(rightOp))
right = Calculate(right, &rightOp, s);
switch(*op){
case '+': left += right; break;
case '-': left -= right; break;
case '*': left *= right; break;
case '/': left /= right; break;
case '^': left = pow(left, right); break;
}
*op = rightOp;
return left;
}
double Solve(char **s){
double value = GetValue(s);
char op = *(*s)++;
while(op != 0 && op != ')')
value = Calculate(value, &op, s);
return value;
}
void Evaluate(char *expression, char *result){
sprintf(result, "%g", Solve(&expression));
}
Since the OP's "reference implementation" is in C#, I wrote a semi-compressed C# version as well:
D P(D o){
return o!=6?o!=7&&o!=2?o<2?0:1:2:3;
}
D T(ref S s){
int i;
if(s[i=0]<48)
i++;
while(i<s.Length&&s[i]>47&s[i]<58|s[i]==46)
i++;
S t=s;
s=s.Substring(i);
return D.Parse(t.Substring(0,i));
}
D V(ref S s,out D o){
D r;
if(s[0]!=40)
r=T(ref s);
else{s=s.Substring(1);r=M(ref s);}
if(s=="")
o=0;
else{o=s[0]&7;s=s.Substring(1);}
return r;
}
void L(ref D v,ref D o,ref S s){
D p,r=V(ref s,out p),u=v;
for(;P(o)<P(p);)
L(ref r,ref p,ref s);
v = new Func<D>[]{()=>u*r,()=>u+r,()=>0,()=>u-r,()=>Math.Pow(u,r),()=>u/r}[(int)o-2]();
o=p;
}
D M(ref S s){
for(D o,r=V(ref s,out o);o>1)
L(ref r,ref o,ref s);
return r;
}
F#, 52 lines
This one mostly eschews generality, and just focuses on writing a recursive descent parser to solve this exact problem.
open System
let rec Digits acc = function
| c::cs when Char.IsDigit(c) -> Digits (c::acc) cs
| rest -> acc,rest
let Num = function
| cs ->
let acc,cs = match cs with|'-'::t->['-'],t |_->[],cs
let acc,cs = Digits acc cs
let acc,cs = match cs with
| '.'::t -> Digits ('.'::acc) t
| _ -> acc, cs
let s = new string(List.rev acc |> List.to_array)
float s, cs
let Chainl p op cs =
let mutable r, cs = p cs
let mutable finished = false
while not finished do
match op cs with
| None -> finished <- true
| Some(op, cs2) ->
let r2, cs2 = p cs2
r <- op r r2
cs <- cs2
r, cs
let rec Chainr p op cs =
let x, cs = p cs
match op cs with
| None -> x, cs
| Some(f, cs) -> // TODO not tail-recursive
let y, cs = Chainr p op cs
f x y, cs
let AddOp = function
| '+'::cs -> Some((fun x y -> 0. + x + y), cs)
| '-'::cs -> Some((fun x y -> 0. + x - y), cs)
| _ -> None
let MulOp = function
| '*'::cs -> Some((fun x y -> 0. + x * y), cs)
| '/'::cs -> Some((fun x y -> 0. + x / y), cs)
| _ -> None
let ExpOp = function
| '^'::cs -> Some((fun x y -> Math.Pow(x,y)), cs)
| _ -> None
let rec Expr = Chainl Term AddOp
and Term = Chainl Factor MulOp
and Factor = Chainr Part ExpOp
and Part = function
| '('::cs -> let r, cs = Expr cs
if List.hd cs <> ')' then failwith "boom"
r, List.tl cs
| cs -> Num cs
let CodeGolf (s:string) =
Seq.to_list s |> Expr |> fst |> string
// Examples
printfn "%s" (CodeGolf "1.1+2.2+10^2^3") // 100000003.3
printfn "%s" (CodeGolf "10+3.14/2") // 11.57
printfn "%s" (CodeGolf "(10+3.14)/2") // 6.57
printfn "%s" (CodeGolf "-1^(-3*4/-6)") // 1
printfn "%s" (CodeGolf "-2^(2^(4-1))") // 256
printfn "%s" (CodeGolf "2*6/4^2*4/3") // 1
printfn "%s" (CodeGolf "3-2-1") // 0
C, 609 characters
(625 including formatted as below to avoid horizontal scrolling, 42 lines if I make it readable.)
double x(char*e,int*p);
D(char c){return c>=48&&c<=57;}
S(char c){return c==43||c==45;}
double h(char*e,int*p){double r=0,s=1,f=0,m=1;int P=*p;if(e[P]==40){
P++;r=x(e,&P);P++;}else if(D(e[P])||S(e[P])){s=S(e[P])?44-e[P++]:s;
while(D(e[P]))r=r*10+e[P++]-48;if(e[P]==46)while(D(e[++P])){f=f*10+e[P]-48;
m*=10;}r=s*(r+f/m);}*p=P;return r;}
double x(char*e,int*p){double r=0,t,d,x,s=1;do{char o=42;t=1;do{d=h(e,p);
while(e[*p]==94){(*p)++;x=h(e,p);d=pow(d,x);}t=o==42?t*d:t/d;o=e[*p];
if(o==42||o==47)(*p)++;else o=0;}while(o);r+=s*t;s=S(e[*p])?44-e[(*p)++]:0;
}while(s);return r;}
double X(char*e){int p=0;return x(e,&p);}
It's my first code golf.
I'm parsing floats myself and the only library function I use is pow.
I corrected errors with multiple elevations to a power and handling of parentheses. I also made the main function X() that takes just a string as argument. It still returns a double, though.
Expanded
42 non-blank lines
double x(char*e, int*p);
D(char c) { return c>=48 && c<=57; }
S(char c) { return c==43 || c==45; }
double h(char*e, int*p) {
double r=0, s=1, f=0, m=1;
int P=*p;
if(e[P]==40) {
P++;
r=x(e, &P);
P++; }
else if(D(e[P]) || S(e[P])) {
s=S(e[P]) ? 44-e[P++] : s;
while(D(e[P]))
r=r*10+e[P++]-48;
if(e[P]==46)
while(D(e[++P])) {
f=f*10+e[P]-48;
m*=10; }
r=s*(r+f/m); }
*p=P;
return r; }
double x(char*e, int*p) {
double r=0, t, d, x, s=1;
do {
char o=42;
t=1;
do {
d=h(e, p);
while(e[*p]==94) {
(*p)++;
x=h(e, p);
d=pow(d, x); }
t=o==42 ? t*d : t/d;
o=e[*p];
if(o==42 || o==47) (*p)++;
else o=0;
} while(o);
r+=s*t;
s=S(e[*p]) ? 44-e[(*p)++] : 0;
} while(s);
return r; }
double X(char*e) {int p=0; return x(e, &p);}
Ruby, now 44 lines
C89, 46 lines
These could be crammed a lot. The C program includes headers that aren't strictly needed and a main() program that some other entries didn't include. The Ruby program does I/O to get the strings, which wasn't technically required...
I realized that the recursive descent parser doesn't really need separate routines for each priority level, even though that's how it's always shown in references. So I revised my previous Ruby entry by collapsing the three binary priority levels into one recursive routine that takes a priority parameter. I added C89 for fun. It's interesting that the two programs have about the same number of lines.
Ruby
puts class RHEvaluator
def setup e
@opByPri, @x, @TOPPRI = [[?+,0],[?-,0],[?*,1],[?/,1],[?^,2]], e, 3
getsym
rhEval 0
end
def getsym
@c = @x[0]
@x = @x.drop 1
end
def flatEval(op, a, b)
case op
when ?* then a*b
when ?/ then a/b
when ?+ then a+b
when ?- then a-b
when ?^ then a**b
end
end
def factor
t = @c
getsym
t = case t
when ?- then -factor
when ?0..?9 then t.to_f - ?0
when ?(
t = rhEval 0
getsym # eat )
t
end
t
end
def rhEval pri
return factor if pri >= @TOPPRI;
v = rhEval pri + 1
while (q = @opByPri.assoc(@c)) && q[1] == pri
op = @c
getsym
v = flatEval op, v, rhEval(pri + 1)
end
v
end
RHEvaluator # return an expression from the class def
end.new.setup gets.bytes.to_a
C89
#include <stdio.h>
#include <math.h>
#include <strings.h>
#define TOPPRI '3'
#define getsym() token = *x++;
const char opByPri[] = "+0-0*1/1^2";
char token, *x;
double rhEval(int);
int main(int ac, char **av) {
x = av[1];
getsym();
return printf("%f\n", rhEval('0')), 0;
}
double flatEval(char op, double a, double b) {
switch (op) {
case '*': return a * b;
case '/': return a / b;
case '+': return a + b;
case '-': return a - b;
case '^': return pow(a, b);
} }
double factor(void) {
double d; char t = token;
getsym();
switch (t) {
case '-': return -factor();
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
return t - '0';
case '(': d = rhEval('0');
getsym();
}
return d;
}
double rhEval(int pri) {
double v; char *q;
if (pri >= TOPPRI)
return factor();
v = rhEval(pri + 1);
while ((q = index(opByPri, token)) && q[1] == pri) {
char op = token;
getsym();
v = flatEval(op, v, rhEval(pri + 1));
}
return v;
}
C (249 characters)
char*c;double m(char*s,int o){int i;c=s;double x=*s-40?strtod(c,&s):m(c+1,0);double y;for(;*c&&c-41;c++){for(i=0;i<7&&*c-"``-+/*^"[i];i++);if(i<7){if(i/2<=o/2){c-=*c!=41;break;}y=m(c+1,i);x=i-6?i-5?i-4?i-3?i-2?x:x-y:x+y:x/y:x*y:pow(x,y);}}return x;}
This is a somewhat-revamped version of my previous version. By using strtod instead of atof (props to P Daddy) I was able to cut it by ~90 chars!
Features
- Supports exponentation, multiplication, division, addition, and subtraction. Note that it DOES NOT support unary minus, since that wasn't mentioned in the spec, even though it was used in the OP's test cases. I thought it was ambiguous enough to leave out
- It's 249 chars long
- Supports double-precision arithmetic
- It's 249 chars long
- Supports PEMDAS, though exponentation associates as "x^y^z"->"(x^y)^z", not as "x^(y^z)"
- Assumes that input isn't garbage. Garbage in, garbage out.
- Did I mention it's 249 chars long? :P
Usage
Pass a pointer to a null-terminated array of chars, then 0. Like so:
m(charPtr,0)
You must include math.h and stdlib.h in the source file you call the function from. Also note that char*c is defined globally at the start of the code. So don't define any variable named c in anything using this. If you must have a way to negate things, "-[insert expression here]" is equivalent to "(0-[insert expression here])" the way the OP has precedence ordered
I know, I know..this code-golf seems to be closed. Still, I felt the urge to code this stuff in erlang __, so here is an erlang version (didn't found the will to golf-format it, so these are 58 lines, about 1400 chars)
-module (math_eval).
-export ([eval/1]).
eval( Str ) ->
ev(number, Str,[]).
ev( _, [], Stack ) -> [Num] = do(Stack), Num;
ev( State, [$ |Str], Stack ) ->
ev( State,Str,Stack );
ev( number, [$(|Str], Stack ) ->
ev( number,Str,[$(|Stack] );
ev( number, Str, Stack ) ->
{Num,Str1} = r(Str),
ev( operator,Str1,[Num|Stack] );
ev( operator, [$)|Str], Stack) ->
ev( operator, Str, do(Stack) );
ev( operator, [Op2|Str], [N2,Op,N1|T]=Stack ) when is_float(N1) andalso is_float(N2) ->
case p(Op2,Op) of
true -> ev( number, Str, [Op2|Stack]);
false -> ev( operator, [Op2|Str], [c(Op,N1,N2)|T] )
end;
ev( operator, [Op|Str], Stack ) ->
ev( number,Str,[Op|Stack] ).
do(Stack) ->
do(Stack,0).
do([],V) -> [V];
do([$(|Stack],V) -> [V|Stack];
do([N2,Op,N1|Stack],0) ->
do(Stack,c(Op,N1,N2));
do([Op,N1|Stack],V) ->
do(Stack,c(Op,N1,V)).
p(O1,O2) -> op(O1) < op(O2).
op(O) ->
case O of
$) -> 0; $( -> 0;
$^ -> 1;
$* -> 2; $/ -> 2;
$+ -> 3; $- -> 3;
$ -> 4; _ -> -1
end.
r(L) ->
r(L,[]).
r([], Out) ->
{f( lists:reverse(Out) ),[]};
r([$-|R],[]) ->
r(R,[$-]);
r([C|T]=R,O) ->
if (C =< $9 andalso C >= $0) orelse C =:= $. -> r(T,[C|O]);
true -> {f(lists:reverse(O)),R}
end.
f(L) ->
case lists:any(fun(C) -> C =:= $. end,L) of
true -> list_to_float(L);
false -> list_to_float(L++".0")
end.
c($+,A,B) -> A+B;
c($-,A,B) -> A-B;
c($*,A,B) -> A*B;
c($/,A,B) -> A/B;
c($^,A,B) -> math:pow(A,B).
This is my "reference implementation" in C# (somewhat unwieldy).
static int RevIndexOf(string S, char Ch, int StartPos)
{
for (int P = StartPos; P >= 0; P--)
if (S[P] == Ch)
return P;
return -1;
}
static bool IsDigit(char Ch)
{
return (((Ch >= '0') && (Ch <= '9')) || (Ch == '.'));
}
static int GetNextOperator(List<string> Tokens)
{
int R = Tokens.IndexOf("^");
if (R != -1)
return R;
int P1 = Tokens.IndexOf("*");
int P2 = Tokens.IndexOf("/");
if ((P1 == -1) && (P2 != -1))
return P2;
if ((P1 != -1) && (P2 == -1))
return P1;
if ((P1 != -1) && (P2 != -1))
return Math.Min(P1, P2);
P1 = Tokens.IndexOf("+");
P2 = Tokens.IndexOf("-");
if ((P1 == -1) && (P2 != -1))
return P2;
if ((P1 != -1) && (P2 == -1))
return P1;
if ((P1 != -1) && (P2 != -1))
return Math.Min(P1, P2);
return -1;
}
static string ParseSubExpression(string SubExpression)
{
string[] AA = new string[] { "--", "++", "+-", "-+" };
string[] BB = new string[] { "+", "+", "-", "-" };
for (int I = 0; I < 4; I++)
while (SubExpression.IndexOf(AA[I]) != -1)
SubExpression = SubExpression.Replace(AA[I], BB[I]);
const string Operators = "^*/+-";
List<string> Tokens = new List<string>();
string Token = "";
foreach (char Ch in SubExpression)
if (IsDigit(Ch) || (("+-".IndexOf(Ch) != -1) && (Token == "")))
Token += Ch;
else
if (Operators.IndexOf(Ch) != -1)
{
Tokens.Add(Token);
Tokens.Add(Ch + "");
Token = "";
}
else
throw new Exception("Unhandled error: invalid expression.");
Tokens.Add(Token);
int P1 = GetNextOperator(Tokens);
while (P1 != -1)
{
double A = double.Parse(Tokens[P1 - 1]);
double B = double.Parse(Tokens[P1 + 1]);
double R = 0;
switch (Tokens[P1][0])
{
case '^':
R = Math.Pow(A, B);
break;
case '*':
R = A * B;
break;
case '/':
R = A / B;
break;
case '+':
R = A + B;
break;
case '-':
R = A - B;
break;
}
Tokens[P1] = R.ToString();
Tokens.RemoveAt(P1 + 1);
Tokens.RemoveAt(P1 - 1);
P1 = GetNextOperator(Tokens);
}
if (Tokens.Count == 1)
return Tokens[0];
else
throw new Exception("Unhandled error.");
}
static bool FindSubExpression(string Expression, out string Left, out string Middle, out string Right)
{
int P2 = Expression.IndexOf(')');
if (P2 == -1)
{
Left = "";
Middle = "";
Right = "";
return false;
}
else
{
int P1 = RevIndexOf(Expression, '(', P2);
if (P1 == -1)
throw new Exception("Unhandled error: unbalanced parentheses.");
Left = Expression.Substring(0, P1);
Middle = Expression.Substring(P1 + 1, P2 - P1 - 1);
Right = Expression.Remove(0, P2 + 1);
return true;
}
}
static string ParseExpression(string Expression)
{
Expression = Expression.Replace(" ", "");
string Left, Middle, Right;
while (FindSubExpression(Expression, out Left, out Middle, out Right))
Expression = Left + ParseSubExpression(Middle) + Right;
return ParseSubExpression(Expression);
}
Ruby, 61 lines, includes console input
puts class RHEvaluator
def setup e
@x = e
getsym
rhEval
end
def getsym
@c = @x[0]
@x = @x.drop 1
end
def flatEval(op, a, b)
case op
when ?* then a*b
when ?/ then a/b
when ?+ then a+b
when ?- then a-b
when ?^ then a**b
end
end
def factor
t = @c
getsym
t = case t
when ?- then -factor
when ?0..?9 then t.to_f - ?0
when ?(
t = rhEval
getsym # eat )
t
end
t
end
def power
v = factor
while @c == ?^
op = @c
getsym
v = flatEval op, v, factor
end
v
end
def multiplier
v = power
while @c == ?* or @c == ?/
op = @c
getsym
v = flatEval op, v, power
end
v
end
def rhEval
v = multiplier
while @c == ?+ or @c == ?-
op = @c
getsym
v = flatEval op, v, multiplier
end
v
end
RHEvaluator # return an expression from the class def
end.new.setup gets.bytes.to_a
C#, 1328 bytes
My first try. It's a full program with console IO.
using System;using System.Collections.Generic;using System.Linq;
using F3 = System.Func<double, double, double>;using C = System.Char;using D = System.Double;
using I = System.Int32;using S = System.String;using W = System.Action;
class F{public static void Main(){Console.WriteLine(new F().EE(Console.ReadLine()));}
D EE(S s){s="("+s.Replace(" ","")+")";
return V(LT(s.Select((c,i)=>c!='-'||P(s[i-1])<0||s[i-1]==')'?c:'_')).GroupBy(t=>t.Item2).Select(g=>new S(g.Select(t=>t.Item1).ToArray())));}
I P(C c){return (" __^^*/+-()".IndexOf(c)-1)/2;}
D V(IEnumerable<S> s){Func<S,C,I>I=(_,c)=>_.IndexOf(c);
I l=0,n=0;var U=new List<S>();var E=new Stack<D>();var O=new Stack<C>();
Func<D>X=E.Pop;Action<D>Y=E.Push;F3 rpow=(x,y)=>Math.Pow(y,x);F3 rdiv=(x,y)=>y/x;
W[]OA={()=>Y(rpow(X(),X())),()=>Y(X()*X()),()=>Y(rdiv(X(),X())),()=>Y(X()+X()),()=>Y(-X()+X()),()=>Y(-X()),};
O.Push(')');foreach(S k in s.TakeWhile(t=>l>0||n==0)){n++;I a=I("(",k[0])-I(")",k[0]);l+=a;
if(l>1||l==-a)U.Add(k);else{if(U.Count>0)E.Push(V(U));U.Clear();I p = Math.Min(P(k[0]),P('-'));
if(p<0)E.Push(D.Parse(k));else{while(P(O.Peek())<=p)OA[I("^*/+-_",O.Pop())]();O.Push(k[0]);}}}
return X();}
IEnumerable<Tuple<C,I>> LT(IEnumerable<C> s){I i=-1,l=-2;foreach(C c in s){I p=P(c);if(p>=0||p!=l)i++;l=P(c);yield return Tuple.Create(c,i);}}}
Here it is un-golfified:
using System;
using System.Collections.Generic;
using System.Linq;
class E
{
public static void Main()
{
Console.WriteLine(EvalEntry(Console.ReadLine()));
}
public static double EvalEntry(string s)
{
return Eval(Tokenize("(" + s.Replace(" ", "") + ")"));
}
const char UnaryMinus = '_';
static int Precedence(char op)
{
// __ and () have special (illogical at first glance) placement as an "optimization" aka hack
return (" __^^*/+-()".IndexOf(op) - 1) / 2;
}
static double Eval(IEnumerable<string> s)
{
Func<string, char, int> I = (_, c) => _.IndexOf(c);
Func<char, int> L = c => I("(", c) - I(")", c);
// level
int l = 0;
// token count
int n = 0;
// subeval
var U = new List<string>();
// evaluation stack
var E = new Stack<double>();
// operation stack
var O = new Stack<char>();
Func<double> pop = E.Pop;
Action<double> push = E.Push;
Func<double, double, double> rpow = (x, y) => Math.Pow(y, x);
Func<double, double, double> rdiv = (x, y) => y / x;
// ^*/+-_
Action[] operationActions =
{
() => push(rpow(pop(), pop())),
() => push(pop()*pop()),
() => push(rdiv(pop(),pop())),
() => push(pop()+pop()),
() => push(-pop()+pop()),
() => push(-pop()),
};
Func<char, Action> getAction = c => operationActions["^*/+-_".IndexOf(c)];
// ohhhhh here we have another hack!
O.Push(')');
foreach (var k in s.TakeWhile(t => l > 0 || n == 0))
{
n++;
int adjust = L(k[0]);
l += L(k[0]);
/* major abuse of input conditioning here to catch the ')' of a subgroup
* (level == 1 && adjust == -1) => (level == -adjust)
*/
if (l > 1 || l == -adjust)
{
U.Add(k);
continue;
}
if (U.Count > 0)
{
E.Push(Eval(U));
U.Clear();
}
int prec = Math.Min(Precedence(k[0]), Precedence('-'));
// just push the number if it's a number
if (prec == -1)
{
E.Push(double.Parse(k));
}
else
{
while (Precedence(O.Peek()) <= prec)
{
// apply op
getAction(O.Pop())();
}
O.Push(k[0]);
}
}
return E.Pop();
}
static IEnumerable<string> Tokenize(string s)
{
return
LocateTokens(PreprocessUnary(s))
.GroupBy(t => t.Item2)
.Select(g => new string(g.Select(t => t.Item1).ToArray()));
}
// make sure the string doesn't start with -
static IEnumerable<char> PreprocessUnary(string s)
{
return s.Select((c, i) => c != '-' || Precedence(s[i - 1]) < 0 || s[i - 1] == ')' ? c : UnaryMinus);
}
static IEnumerable<Tuple<char, int>> LocateTokens(IEnumerable<char> chars)
{
int i = -1;
int lastPrec = -2;
foreach (char c in chars)
{
var prec = Precedence(c);
if (prec >= 0 || prec != lastPrec)
{
i++;
lastPrec = Precedence(c);
}
yield return Tuple.Create(c, i);
}
}
}
I wrote an attp at http://www.sumtree.com as an educational tool for teachers that does this.
Used bison for the parsing and wxwidgets for the GUI.
