Calculating the value of an expression

In continuation of the post Expression Compiler . At the request of readers. Especially for michurin

There are many ways to calculate the value of an expression I like most about the two-stack method.
Like for its elegance and ease of implementation.

The essence of the 2-stack method (surely it has a beautiful scientific name.) Is that any difficult expression ultimately boils down to a sequence of simple operations . In our case, this will be a binary operation on the operands A and B.
')
We will go from left to right, adding operands to one stack, and operations to another. Each time a new operation is added, we will try to push the old ones out of the stack, guided by the priorities of the operations. (It is important to note that this is where you can pervert and do everything in 1 stack, but we will stick to the classics)

Since the words Operator and Operand are very similar, we will use Function instead of Operator .
The stack of operands will be called Q
Operator stack W

A simple example:
2 + 2 * 3 - 4

1. 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={}
2. 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={}
3. 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={}
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={}
5. 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={}
6. 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={}
7. 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={}
8. 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={}

For example, take the operations + - * / and brackets.
y * and / priority will be equal to 1
y + and - will be equal to 2
the opening bracket has a priority of -1 and it does not push anyone out.
A closing bracket pushes all operations up to the first one that opens.

Example: 2 + 1 - 6 / (1 + 2)
Consider the example in steps:

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. 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 – , .
3. 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 – , .
4. 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 – , .
5. 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 – , .
6. 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 – , .
7. 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 – , .
8. 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 – , .
9. 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 – , .
10. 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 – , .
11. 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 – , .
12. 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 – , .
13. 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 – , .

In order not to bother with unary operations, we will use the fact that any unary one can be turned into binary. for example, add one as the second operand (the neutral element)
those. instead of (-2) we will have (0 - 2)

Algorithm in 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 .

This is an elementary example that supports only 4 operations. But it is very easy to supplement it with && || ^ & | div mod simply by giving them priority and writing the implementation.

You can add variables. The same algorithm can be used to build trees. Moreover, the trees will be as computed as possible. ie, constant branches (not containing variables) can be calculated in advance.

Very easy to add operator comma.
(2, 4 + 5, 4) will turn into an array {2, 9, 4}

Functions F (x1, x2, ..., xn) is a unary operation on the array {x1, x2, ..., xn}

If you liked the post, next I will write about how I did a small functional language and object-oriented language.