式の値を計算するには多くの方法がありますが、私は2スタック方式が最も好きです。
その優雅さと実装の容易さのように。
2スタックのメソッドの本質は（確かに美しい科学名を持っていることです。） 複雑な表現は、最終的には一連の単純な操作になります。 私たちの場合、これはオペランドAとBの2項演算になります。
左から右に進み、オペランドを1つのスタックに追加し、操作を別のスタックに追加します。 新しい操作が追加されるたびに、操作の優先順位に従って、古い操作をスタックからプッシュしようとします。 （ここではまったく同じであり、1スタックですべてを変更して実行できますが、クラシックに固執することに注意することが重要です）
演算子OperatorとOperandは非常に似ているので、 Operatorの代わりにFunctionを使用します。
オペランドのスタックはQと呼ばれます
演算子スタックW
簡単な例：
2 + 2 * 3-4
-
Q.Push(2) Q 2 W.Push(+) W + Q.Push(2) W.Push(*). W + *. + , * . Q.Push(3) W.Push(-)
– *, , *. 2 AB.
B <- Q.pop()
A <- Q.pop()
Q.push(A - B)
, . Q = {8, 4} W={-}
, , . Q = {4} W={}
-
Q.Push(2) Q 2 W.Push(+) W + Q.Push(2) W.Push(*). W + *. + , * . Q.Push(3) W.Push(-)
– *, , *. 2 AB.
B <- Q.pop()
A <- Q.pop()
Q.push(A - B)
, . Q = {8, 4} W={-}
, , . Q = {4} W={}
-
Q.Push(2) Q 2 W.Push(+) W + Q.Push(2) W.Push(*). W + *. + , * . Q.Push(3) W.Push(-)
– *, , *. 2 AB.
B <- Q.pop()
A <- Q.pop()
Q.push(A - B)
, . Q = {8, 4} W={-}
, , . Q = {4} W={}
-
Q.Push(2) Q 2 W.Push(+) W + Q.Push(2) W.Push(*). W + *. + , * . Q.Push(3) W.Push(-)
– *, , *. 2 AB.
B <- Q.pop()
A <- Q.pop()
Q.push(A - B)
, . Q = {8, 4} W={-}
, , . Q = {4} W={}
-
Q.Push(2) Q 2 W.Push(+) W + Q.Push(2) W.Push(*). W + *. + , * . Q.Push(3) W.Push(-)
– *, , *. 2 AB.
B <- Q.pop()
A <- Q.pop()
Q.push(A - B)
, . Q = {8, 4} W={-}
, , . Q = {4} W={}
-
Q.Push(2) Q 2 W.Push(+) W + Q.Push(2) W.Push(*). W + *. + , * . Q.Push(3) W.Push(-)
– *, , *. 2 AB.
B <- Q.pop()
A <- Q.pop()
Q.push(A - B)
, . Q = {8, 4} W={-}
, , . Q = {4} W={}
-
Q.Push(2) Q 2 W.Push(+) W + Q.Push(2) W.Push(*). W + *. + , * . Q.Push(3) W.Push(-)
– *, , *. 2 AB.
B <- Q.pop()
A <- Q.pop()
Q.push(A - B)
, . Q = {8, 4} W={-}
, , . Q = {4} W={}
-
Q.Push(2) Q 2 W.Push(+) W + Q.Push(2) W.Push(*). W + *. + , * . Q.Push(3) W.Push(-)
– *, , *. 2 AB.
B <- Q.pop()
A <- Q.pop()
Q.push(A - B)
, . Q = {8, 4} W={-}
, , . Q = {4} W={}
たとえば、操作+-* /を使用し、角かっこを使用します。
y *および/は優先度1になります
y +および-は2に等しくなります
開始ブラケットの優先度は-1であり、誰もプッシュしません。
閉じ括弧は、すべての操作を最初の開口部にプッシュします。
例： 2 + 1-6 /（1 + 2）
手順の例を検討してください。
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
-
Q.push(2)
Q = {2}
W = { } W.push(+)
Q = {2}
W = {+} Q.push(1)
Q = {2, 1}
W = {+} W.push(-)
+ – , +
Q = {3}
W = {-} Q.push(6)
Q = {3, 6}
W = {-} W.push( / )
Q = {3, 6}
W = {-, /} W.push( ( )
,
Q = {3, 6}
W = {-, /, (} Q.push(1)
Q = {3, 6, 1}
W = {-, /, (} W.push(+)
. .
Q = {3, 6, 1}
W = {-, /, (, +} Q.push(2)
Q = {3, 6, 1, 2}
W = {-, /, (, +} W.push( ) )
( )
Q = {3, 6, 3}
W = {-, /} ,
Q = {3, 2, 3}
W = {-, /} Q = {1}
W = {}
. 1 – , .
単項演算を気にしないために、単項をバイナリに変換できるという事実を利用します。 たとえば、第2オペランドとしてユニット （中立要素）を追加します。
つまり （-2）の代わりに（0-2）が得られます
C＃アルゴリズム：
public static double Calc( string s)
{
s = '(' + s + ')' ;
Stack< double > Operands = new Stack< double >();
Stack< char > Functions = new Stack< char >();
int pos = 0;
object token;
object prevToken = '' ;
do
{
token = getToken(s, ref pos);
// + -
if (token is char && prevToken is char &&
// (char)prevToken != ')' &&
// (2 * -5) (2 - -4)
// , 2 + -+-+-+2 :)
( char )prevToken == '(' &&
(( char )token == '+' || ( char )token == '-' ))
Operands.Push(0); //
if (token is double ) //
{
Operands.Push(( double )token); //
}
// . , .. ..
else if (token is char ) //
{
if (( char )token == ')' )
{
// - .
while (Functions.Count > 0 && Functions.Peek() != '(' )
popFunction(Operands, Functions);
Functions.Pop(); // "("
}
else
{
while (canPop(( char )token, Functions)) //
popFunction(Operands, Functions); //
Functions.Push(( char )token); //
}
}
prevToken = token;
}
while (token != null );
if (Operands.Count > 1 || Functions.Count > 0)
throw new Exception( " " );
return Operands.Pop();
}
private static void popFunction(Stack< double > Operands, Stack< char > Functions)
{
double B = Operands.Pop();
double A = Operands.Pop();
switch (Functions.Pop())
{
case '+' : Operands.Push(A + B);
break ;
case '-' : Operands.Push(A - B);
break ;
case '*' : Operands.Push(A * B);
break ;
case '/' : Operands.Push(A / B);
break ;
}
}
private static bool canPop( char op1, Stack< char > Functions)
{
if (Functions.Count == 0)
return false ;
int p1 = getPriority(op1);
int p2 = getPriority(Functions.Peek());
return p1 >= 0 && p2 >= 0 && p1 >= p2;
}
private static int getPriority( char op)
{
switch (op)
{
case '(' :
return -1; //
case '*' : case '/' :
return 1;
case '+' : case '-' :
return 2;
default :
throw new Exception( " " );
}
}
private static object getToken( string s, ref int pos)
{
readWhiteSpace(s, ref pos);
if (pos == s.Length) //
return null ;
if ( char .IsDigit(s[pos]))
return Convert .ToDouble(readDouble(s, ref pos));
else
return readFunction(s, ref pos);
}
private static char readFunction( string s, ref int pos)
{
//
// == && || mod div
return s[pos++];
}
private static string readDouble( string s, ref int pos)
{
string res = "" ;
while (pos < s.Length && ( char .IsDigit(s[pos]) || s[pos] == '.' ))
res += s[pos++];
return res;
}
// .
private static void readWhiteSpace( string s, ref int pos)
{
while (pos < s.Length && char .IsWhiteSpace(s[pos]))
pos++;
}
* This source code was highlighted with Source Code Highlighter .
これは、4つの操作のみをサポートする基本的な例です。 しかし、操作&& ||で補足するのは非常に簡単です。 ^＆| div modに優先度を与え、実装を記述するだけです。
変数を追加できます。 同じアルゴリズムを使用してツリーを構築できます。 さらに、ツリーは可能な限り計算されます。 つまり、永続的な分岐（変数を含まない）は事前に計算できます。
カンマ演算子は非常に簡単に追加できます。
（2、4 + 5、4）は配列{2、9、4}になります
関数F（x1、x2、...、xn）は、配列{x1、x2、...、xn}の単項演算です。
この投稿が気に入ったら、次の投稿で、小さな関数型言語とオブジェクト指向言語の作成方法について書きます。