Code Golf: Mathematical expression evaluator (that respects PEMDAS)?

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 ti #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 t99; 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 tokenList99; 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 */ tokenListi = strtod(expression, &parseEnd); /* explanation below code */ if(parseEnd! = expression && prevOperator! = 4/*constant*/ && prevOperator!

= 1/*close paren*/){ expression = parseEnd; prevOperator = tokenListi + 1 = 4/*constant*/; }else{ /* it's an operator */ prevOperator = tokenListi + 1 = *expression & 7; expression++; } } /* done parsing, add end-of-token-string operator */ tokenListi + 1 = 8/*end*/ /* Evaluate the expression in the token list */ EvalTokens(tokenList + 2); /* remember the offset by 2 above? */ sprintf(result, "%g", tokenList0/* 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; tokenListi + 1! = 8/*end*/; i+= 2) if(tokenListi + 1 == 0/*open paren*/) for(parenLevel = 1, parenStart = i; I += 2, parenLevel > 0){ if(tokenListi + 1 == 0/*another open paren*/) parenLevel++; else if(tokenListi + 1 == 1/*close paren*/) if(--parenLevel == 0){ /* make this a temporary end of list */ tokenListi + 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; tokenListi + 1!

= 8/*end*/; i+= 2) if(tokenListi + 1 == 6/*exponentiation operator (^)*/){ tokenListi - 2 = pow(tokenListi - 2, tokenListi + 2); FoldTokens(tokenList + I - 2, 4); I -= 2; } for(i = 0; tokenListi + 1! = 8/*end*/; i+= 2) if(tokenListi + 1 == 2/*multiplication operator (*)*/ || tokenListi + 1 == 7/*division operator (/)*/){ tokenListi - 2 *= (tokenListi + 1 == 2? TokenListi + 2 : 1 / tokenListi + 2); FoldTokens(tokenList + I - 2, 4); I -= 2; } for(i = 0; tokenListi + 1!

= 8/*end*/; i+= 2) if(tokenListi + 1! = 4/*constant*/){ tokenListi - 2 += (tokenListi + 1 == 3? TokenListi + 2 : -tokenListi + 2); FoldTokens(tokenList + I - 2, 4); I -= 2; } tokenList-2 = tokenList0; /* the compressed code does the above in a loop, equivalent to: * * for(i = 0; tokenListi + 1!

= 8; i+= 2) * tokenListi - 2 = tokenListi; * * 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++; tokenList0 = 4; // force value to constant while(tokenList0!

= 8/*end of token string*/){ tokenList0 = tokenListoffset; tokenList1 = tokenListoffset + 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().

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 , , and (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 ti #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 t99; 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 tokenList99; 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 */ tokenListi = strtod(expression, &parseEnd); /* explanation below code */ if(parseEnd! = expression && prevOperator!

= 4/*constant*/ && prevOperator! = 1/*close paren*/){ expression = parseEnd; prevOperator = tokenListi + 1 = 4/*constant*/; }else{ /* it's an operator */ prevOperator = tokenListi + 1 = *expression & 7; expression++; } } /* done parsing, add end-of-token-string operator */ tokenListi + 1 = 8/*end*/ /* Evaluate the expression in the token list */ EvalTokens(tokenList + 2); /* remember the offset by 2 above? */ sprintf(result, "%g", tokenList0/* 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; tokenListi + 1! = 8/*end*/; i+= 2) if(tokenListi + 1 == 0/*open paren*/) for(parenLevel = 1, parenStart = i; I += 2, parenLevel > 0){ if(tokenListi + 1 == 0/*another open paren*/) parenLevel++; else if(tokenListi + 1 == 1/*close paren*/) if(--parenLevel == 0){ /* make this a temporary end of list */ tokenListi + 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; tokenListi + 1!

= 8/*end*/; i+= 2) if(tokenListi + 1 == 6/*exponentiation operator (^)*/){ tokenListi - 2 = pow(tokenListi - 2, tokenListi + 2); FoldTokens(tokenList + I - 2, 4); I -= 2; } for(i = 0; tokenListi + 1! = 8/*end*/; i+= 2) if(tokenListi + 1 == 2/*multiplication operator (*)*/ || tokenListi + 1 == 7/*division operator (/)*/){ tokenListi - 2 *= (tokenListi + 1 == 2? TokenListi + 2 : 1 / tokenListi + 2); FoldTokens(tokenList + I - 2, 4); I -= 2; } for(i = 0; tokenListi + 1!

= 8/*end*/; i+= 2) if(tokenListi + 1! = 4/*constant*/){ tokenListi - 2 += (tokenListi + 1 == 3? TokenListi + 2 : -tokenListi + 2); FoldTokens(tokenList + I - 2, 4); I -= 2; } tokenList-2 = tokenList0; /* the compressed code does the above in a loop, equivalent to: * * for(i = 0; tokenListi + 1!

= 8; i+= 2) * tokenListi - 2 = tokenListi; * * 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++; tokenList0 = 4; // force value to constant while(tokenList0!

= 8/*end of token string*/){ tokenList0 = tokenListoffset; tokenList1 = tokenListoffset + 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 t99; 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 t99; 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.

There went the C solution I was working on. Oh well, wonder if I can do this in Perl without regexes... – Chris Lutz Sep 7 '09 at 1:42 I don't think naming the struct is necessary. Thus, you can remove the _ and the space before it.(I could be wrong.) Also, you need to include stdio.

H at least for the library functions you use.(Not sure about the math functions. ) I definitely can't tell what's going on, but good job. ;P – strager Sep 7 '09 at 1:50 Hmm, would it be smaller to rewrite x?(V=a):(V=c) as V=x?

A:c in E's for loop? Also, maybe you can use & instead of && and | instead of || for some cases. – strager Sep 7 '09 at 1:52 @strager: Thanks for the tip about removing the name of the struct.

As for stdio. H, I still hold that, since a function was asked for, not a complete program, the includes can be left out, and if you take yours out, your code will be smaller than mine The ternary in E includes 2 assignments: to V and to P. I can either put the P= or the V= before the?.

Since what's assigned to P is also assigned to d, it's better to have that. I've been looking for more cases where &&/|| can be converted to &/|, but I'm not sure there are more. Let me know if you see any.

– P Daddy Sep 7 '09 at 1:59 On the whole includes thing, I see your point. However, for C, I think it's appropriate to provide an entire, compiling file for code golf solutions. I'll try playing with your code myself to see if anything more can be done.

= – strager Sep 7 '09 at 2:02.

C#, 13 lines: static string Calc(string exp) { WebRequest request = WebRequest. Create("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("Substring(start, end - start); } } This compresses down to about 317 characters: static string C(string e){var q = WebRequest.

Create("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("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 ("google.com/search?q="+HttpUtility.

UrlDecode(f));int s=r. IndexOf( " = ")+3;return r. Substring(s,r.

IndexOf(".

5 This wins. This is so much better than all the other answers where you can't understand a thing taking place. – jdelator Sep 7 '09 at 1:46 27 I don't think it wins, it goes against the spirit of the question, since the answer is practicly using an exisitng eval function.

– hhafez Sep 7 '09 at 2:05 4 I wish I could vote up twice. – Jed Smith Sep 7 '09 at 2:08 4 Outsourcing the answer :D – gw. Sep 7 '09 at 3:21 7 So, I can choose any "programming language" and program it?

If so, if you accept this solution, you should also allow me to install "unix bc" calculator as my development environment, and then my solution is echo "" | bc -l This solution violates the "use an eval library from somewhere". – Ira Baxter Sep 7 '09 at 9:53.

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 = char list -> option by the way, a common one for non-error-handling parsers.

1 +1, I just wanted to say this has inspired me to take another look at F#. – Andrew Walker Sep 6 '09 at 8:26 Handles -(2+3)? Handles 1E7?

– Ira Baxter Sep 6 '09 at 8:35 It handles neither of those. Unary minus before an expression does not seem to be part of the spec. The '1e7' stuff is optional and I chose not to do it.

– Brian Sep 6 '09 at 8:57.

5 That's the third formatting edit I've done today. On a more relevant note, does anyone seriously use J for anything other than winning at code golf? If so, are you a masochist?

– Chris Lutz Sep 7 '09 at 1:44 2 Damnit, J! – P Daddy Sep 7 '09 at 2:48 5 And that actually does something, other than sticking its tongue out at you? – P Daddy Sep 7 '09 at 2:49 2 Okay, I had to know, so I downloaded J602.

I have no idea what I'm doing, mind you, but when I paste your code in and try to run it, it says "spelling error", and points to the first parenthesis (character 6, 0-based). – P Daddy Sep 7 '09 at 5:15 3 Oh, wait. I just got the joke.

Alex: "let me have a try at J: :(::(:o:pO_O&i-:)$$. Did I make a program? " (stackoverflow.Com/questions/1376077/code-golf-the-wave/…) – P Daddy Sep 7 '09 at 5:17.

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}.

1 for posting an answer to a closed question. Wish I had the sneakiness to pull that one off. – Chris Lutz Sep 6 '09 at 5:00 Couldn't let a ding go by... – Ira Baxter Sep 6 '09 at 5:04.

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|_->Ds)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.

2 +1: Eyes explode – Juliet Sep 8 '09 at 15:13.

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 { public T Value { get; set; } public Option(T x) { Value = x; } } delegate Option>> P(List input); static class Program { static List Cons(T x, List xs) { var r = new List(xs); r. Insert(0, x); return r; } static Option Some(T x) { return new Option(x); } static KeyValuePair KVP(T x, List y) { return new KeyValuePair(x,y); } // Core Parser Library static P Fail() { return I => null; } static P Select(this P p, Func 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 SelectMany(this P p, Func sel, Func 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 Or(this P p1, P p2) { return I => { var r = p1(i); if (r == null) return p2(i); return r; }; } static P Sat(Func pred) { return I => { if (i. Count == 0 ||! Pred(i0)) return null; var rest = new List(i); rest.

RemoveAt(0); return Some(KVP(i0, rest)); }; } static P Return(T x) { return I => Some(KVP(x,i)); } // Auxiliary Parser Library static P Digit = Sat(Char. IsDigit); static P Lit(char c, T r) { return from dummy in Sat(x => x == c) select r; } static P Opt(P p) { return p. Or(Return(new List())); } static P Many(P p) { return Many1(p).

Or(Return(new List())); } static P Many1(P p) { return from x in p from xs in Many(p) select Cons(x, xs); } static P Chainl1(this P p, P> op) { return from x in p from r in Chainl1Helper(x, p, op) select r; } static P Chainl1Helper(T x, P p, P> 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 Chainr1(this P p, P> 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 TryParse(string s) { double d; if (Double.

TryParse(s, out d)) return Return(d); return Fail(); } static void Main(string args) { var Num = from WriteLine(CodeGolf("2*6/4^2*4/3")); // 1 } }.

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 #include #include float X(char*c){ struct{ float f; int d,c; }N99,*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(*cd=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. =.

I would assume that the #includes aren't required, since only a function was called for. And it should compile and run without them, anyway. – P Daddy Sep 7 '09 at 1:13 2 @P Daddy, Not true.

Without them, the function signatures would not be there. This would mean a double would be passed to powf, an int passed where a char * is expected, etc. It cannot be assumed a pointer fits in an int, for example. – strager Sep 7 '09 at 1:33.

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(*p47&si{()=>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 let r2, cs2 = p cs2 r 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=48 && cT*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);}.

OK, arguments are a string and the pointer to a counter indicating where to start, and it returns a double. Mayble I'll modify it later to take just a string and return a string as per the rules. – Olivier 'Ölbaum' Scherler Sep 6 '09 at 13:11 Ooops, I still have errors.Be back.

– Olivier 'Ölbaum' Scherler Sep 6 '09 at 13:17 Back. Fixed errors. – Olivier 'Ölbaum' Scherler Sep 6 '09 at 13:47 1 Done, but looking at the previous code golfs, absence of format seemed reasonable too.

– Olivier 'Ölbaum' Scherler Sep 6 '09 at 19:14 1 Yeah, my personal rule of thumb for code-golf is, if you can get it under 1000 characters, then forget formatting and get it to minimal characters and use 'character count' to advertise your score. Otherwise, format code well, and use 'line count' to advertise your score. – Brian Sep 6 '09 at 21:11.

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 = @x0 @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)) && q1 == 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 #include #include #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 = av1; 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)) && q1 == pri) { char op = token; getsym(); v = flatEval(op, v, rhEval(pri + 1)); } return v; }.

Strtod(c,&s):m(c+1,0);double y;for(;*c&&c-41;c++){for(i=0;i"(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.

You seem to still have a bug or two. It fails every test expression I throw at it, including the three posted by the OP. It also blows up for me with an access violation if you feed it a constant, since I tries to write to read-only memory.

That's some pretty tiny code, though. If you can get it working and still keep it small, it can be shrunk down quite a bit from what it is. Using simple techniques, I got it down to 290 without changing semantics.

– P Daddy Sep 11 '09 at 0:04 Plus I should add that to work around atof evaluating +/- I had to write some code to temporarily change the operator the loop was currently working on to 0, then change it back. That might be why you're getting the access violation. – sobellian Sep 11 '09 at 0:47 Oh, I figured out what you were trying to do :P This doesn't support unary minus, as it wasn't mentioned in the 'clarifications' section even though the other operators were.

I figured You could create a functional equivalent of "-n" with "(0-n)" anyway, so yeah. – sobellian Sep 11 '09 at 0:59 strtod would fix a lot of your problems. Your current code is returning zero for all inputs, by the way.

– P Daddy Sep 11 '09 at 13:39 Hmm. For me, it compiled fine with GCC. My current code passed all the test cases I fed it – sobellian Sep 11 '09 at 21:10.

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) 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 == $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 (SP == Ch) return P; return -1; } static bool IsDigit(char Ch) { return (((Ch >= '0') && (Ch 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 Tokens = new List(); 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(TokensP1 - 1); double B = double.

Parse(TokensP1 + 1); double R = 0; switch (TokensP10) { 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; } TokensP1 = R.ToString(); Tokens. RemoveAt(P1 + 1); Tokens.

RemoveAt(P1 - 1); P1 = GetNextOperator(Tokens); } if (Tokens. Count == 1) return Tokens0; 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); }.

You ought to add size statistics for comparative purposes (lines, chars). – Ira Baxter Sep 6 '09 at 6:09 120 non-blank lines. There's plenty of room for optimization yet.

– gw. Sep 6 '09 at 6:21 Are you counting a single { or } as a non-blank line? – Robert L Sep 6 '09 at 6:25 I included the braces when counting lines.

Although the line count for this particular implementation doesn't really matter. – gw. Sep 6 '09 at 3:22.

Ruby, 61 lines, includes console input puts class RHEvaluator def setup e @x = e getsym rhEval end def getsym @c = @x0 @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;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(si-1)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){FuncI=(_,c)=>_.

IndexOf(c); I l=0,n=0;var U=new List();var E=new Stack();var O=new Stack(); FuncX=E. Pop;ActionY=E. Push;F3 rpow=(x,y)=>Math.

Pow(y,x);F3 rdiv=(x,y)=>y/x; WOA={()=>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("(",k0)-I(")",k0);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(k0),P('-')); if(p> LT(IEnumerable 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 s) { Func I = (_, c) => _. IndexOf(c); Func L = c => I("(", c) - I(")", c); // level int l = 0; // token count int n = 0; // subeval var U = new List(); // evaluation stack var E = new Stack(); // operation stack var O = new Stack(); Func pop = E.

Pop; Action push = E. Push; Func rpow = (x, y) => Math. Pow(y, x); Func 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 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(k0); l += L(k0); /* 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(k0), Precedence('-')); // just push the number if it's a number if (prec == -1) { E. Push(double.

Parse(k)); } else { while (Precedence(O.Peek()) t. Item2) . Select(g => new string(g.

Select(t => t. Item1).ToArray())); } // make sure the string doesn't start with - static IEnumerable PreprocessUnary(string s) { return s. Select((c, i) => c!

= '-' || Precedence(si - 1) LocateTokens(IEnumerable 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 sumtree.com as an educational tool for teachers that does this. Used bison for the parsing and wxwidgets for the GUI.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.