C (465 文字)
#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);}
最初の 5 つの改行は必須で、残りは読みやすくするためだけにあります。最初の 5 つの改行をそれぞれ 1 文字としてカウントしました。行数で測ると、空白をすべて削除する前は 28 行でしたが、これはかなり無意味な数値です。どのようにフォーマットしたかによって、6 行から 100 万行になる可能性があります。
エントリ ポイントはE()(「評価する」) です。最初のパラメーターは入力文字列で、2 番目のパラメーターは出力文字列を指し、呼び出し元によって割り当てられる必要があります (通常の C 標準に従って)。最大 47 個のトークンを処理できます。トークンは演算子 (" +-*/^()" のいずれか) または浮動小数点数です。単項演算子は、個別のトークンとしてカウントされません。
このコードは、何年も前に演習として行ったプロジェクトに大まかに基づいています。エラー処理と空白のスキップをすべて取り除き、ゴルフのテクニックを使って再構築しました。以下は 28 行で、私が書くには十分な形式ですが、おそらく読むには十分ではありません。#include <stdlib.h>、<stdio.h>、および<math.h>(または下部の注を参照) を実行する必要があります。
それがどのように機能するかの説明については、コードの後に参照してください。
#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);
}
最初のステップはトークン化です。double の配列には、トークンごとに 2 つの値、演算子 (ゼロに非常に似ているPため) と値 ( ) が含まれます。このトークン化は、 のループで行われます。また、単項演算子と演算子を扱い、それらを定数に組み込みます。OVforE()+-
トークン配列の「operator」フィールドには、次のいずれかの値を指定できます。
0 : (
1 : )
2 : *
3 : +
4 :浮動小数点定数値
5 : -
6 : ^
7 : /
8 :トークン文字列の終わり
このスキームの大部分は Daniel Martin によって導き出されました。Daniel Martinは、この課題の各演算子の ASCII 表現で最後の 3 ビットが一意であることに気付きました。
の非圧縮バージョンは次のE()ようになります。
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 */);
}
有効な入力が保証されているため、解析が失敗する唯一の理由は、次のトークンが演算子であるためです。この場合、parseEndポインターは と同じになりますtokenStart。解析が成功した場合も処理する必要がありますが、本当に必要なのは演算子でした。これは、符号演算子が直接続かない限り、加算演算子と減算演算子で発生します。つまり、式 " " が与えられた場合、としてではなく として4-6解析したいと考えています。一方、「」が与えられた場合、 として解析する必要があります。解決策は非常に簡単です。解析に失敗した場合OR{4, -, 6}{4, -6}4+-6{4, +, -6}前のトークンが定数または閉じ括弧 (事実上、定数に評価される部分式) であった場合、現在のトークンは演算子であり、それ以外の場合は定数です。
トークン化が完了した後、 を呼び出すことによって計算と折り畳みが行われM()ます。これは、最初に一致する括弧のペアを探し、それ自体を再帰的に呼び出すことによって、その中に含まれる部分式を処理します。次に演算子を処理し、最初に累乗、次に乗算と除算をまとめて処理し、最後に加算と減算をまとめて処理します。(チャレンジで指定されているように) 整形式の入力が期待されるため、他のすべてが処理された後の最後の正当な演算子であるため、追加演算子を明示的にチェックしません。
ゴルフ圧縮がない計算関数は、次のようになります。
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. */
}
ある程度圧縮すると、おそらくこの関数が読みやすくなります。
演算が実行されると、オペランドと演算子はK()(マクロSを介して呼び出される) によってトークン リストから折り畳まれます。演算の結果は、折り畳まれた式の代わりに定数として残されます。その結果、最終結果はトークン配列の先頭に残されるため、制御が に戻るとE()、配列の最初の値がトークンの値フィールドであるという事実を利用して、単純にそれを文字列に出力します。
この への呼び出しFoldTokens()は、操作 ( ^、*、/、+、または-) が実行された後、または部分式 (括弧で囲まれた) が処理された後に行われます。このFoldTokens()ルーチンは、結果の値が正しい演算子型 (4) であることを確認してから、部分式の残りのより大きな式をコピーします。たとえば、式 " 2+6*4+1" が処理されると、EvalTokens()最初に が計算され、結果が( )6*4の代わりに残されます。 次に、部分式 " " の残りを削除して、 を残します。62+24*4+1FoldTokens()24*42+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;
}
}
それでおしまい。マクロは一般的な操作を置き換えるためのものであり、他のすべては上記の単純な圧縮です。
stragerは、 andおよび 関数#includeの適切な前方宣言がないと正しく機能しないため、コードにステートメントを含める必要があると主張しています。課題は完全なプログラムではなく機能のみを要求するため、これは必須ではないと考えています。ただし、次のコードを追加することで、最小限のコストで前方宣言を追加できます。strtodpow
#define D double
D strtod(),pow();
double次に、コード内の " "のすべてのインスタンスを " " に置き換えますD。これにより、コードに 19 文字が追加され、合計で 484 文字になります。一方、彼が行ったように、文字列の代わりに double を返すように関数を変換することもできます。これにより、15 文字が削除され、E()関数がこれ：
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;
}
strtodこれにより、コードの合計サイズは 469 文字になります (または、との前方宣言なしでマクロを使用すると 452 文字にpowなりDます)。呼び出し元に戻り値の double へのポインターを渡すように要求することで、さらに 1 文字をトリミングすることもできます。
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;
}
どのバージョンが適切かを判断するのは読者に任せます。