1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240
|
/**
* @file evaluate.cpp
*/
/*
* This program source code file is part of KiCad, a free EDA CAD application.
*
* Copyright (C) 1992-2017 Jean-Pierre Charras <jp.charras at wanadoo.fr>
* Copyright The KiCad Developers, see AUTHORS.txt for contributors.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you may find one here:
* http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
* or you may search the http://www.gnu.org website for the version 2 license,
* or you may write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
*/
/* How to evaluate an arithmetic expression like those used in Aperture Macro Definition in Gerber?
*
* See http://stackoverflow.com/questions/28256/equation-expression-parser-with-precedence
*
* The shunting yard algorithm is the right tool for this.
* Wikipedia is really confusing about this, but basically the algorithm works like this:
*
* Say, you want to evaluate 1 + 2 * 3 + 4. Intuitively, you "know" you have to do the 2 * 3 first,
* but how do you get this result?
* The key is to realize that when you're scanning the string from left to right, you will evaluate
* an operator when the operator that follows it has a lower (or equal to) precedence.
*
* In the context of the example, here's what you want to do:
*
* Look at: 1 + 2, don't do anything.
* Now look at 1 + 2 * 3, still don't do anything.
* Now look at 1 + 2 * 3 + 4, now you know that 2 * 3 has to to be evaluated because
* the next operator has lower precedence.
*
* How do you implement this?
*
* You want to have two stacks, one for numbers, and another for operators.
* You push numbers onto the stack all the time.
* You compare each new operator with the one at the top of the stack,
* if the one on top of the stack has higher priority, you pop it off the operator stack,
* pop the operands off the number stack, apply the operator and push the result onto the number stack.
*
* Now you repeat the comparison with the top of stack operator.
*
* Coming back to the example, it works like this:
*
* N = [ ] Ops = [ ]
*
* Read 1. N = [1], Ops = [ ]
* Read +. N = [1], Ops = [+]
* Read 2. N = [1 2], Ops = [+]
* Read *. N = [1 2], Ops = [+ *]
* Read 3. N = [1 2 3], Ops = [+ *]
* Read +. N = [1 2 3], Ops = [+ *]
* Pop 3, 2 and execute 2*3, and push result onto N. N = [1 6], Ops = [+]
* is left associative, so you want to pop 1, 6 off as well and execute the +. N = [7], Ops = [].
* Finally push the [+] onto the operator stack. N = [7], Ops = [+].
* Read 4. N = [7 4]. Ops = [+].
*
* You're run out off input, so you want to empty the stacks now.
* Upon which you will get the result 11.
*/
#include <am_param.h>
/**
* Evaluate an basic arithmetic expression (infix notation) with precedence
* The expression is a sequence of numbers (double) and arith operators:
* operators are + - x / ( and )
* the expression is stored in a std::vector
* each item is a AM_PARAM_EVAL (each item is an operator or a double)
* @param aExp = the arithmetic expression to evaluate
* @return the value
*/
/*
The instructions ( subset of parm_item_type)
----------------
NOP : The no operation. the AM_PARAM_EVAL item stores a value.
ADD
SUB
MUL
DIV
OPEN_PAR : Opening parenthesis: modify the precedence of operators inside ( and )
CLOSE_PAR : Closing parenthesis: modify the precedence of operators by closing the local block.
POPVALUE : used to initialize a sequence
*/
double Evaluate( AM_PARAM_EVAL_STACK& aExp )
{
class OP_CODE // A small class to store a operator and its priority
{
public:
parm_item_type m_Optype;
int m_Priority;
OP_CODE( AM_PARAM_EVAL& aAmPrmEval )
: m_Optype( aAmPrmEval.GetOperator() ),
m_Priority( aAmPrmEval.GetPriority() )
{}
OP_CODE( parm_item_type aOptype )
: m_Optype( aOptype ), m_Priority( 0 )
{}
};
double result = 0.0;
std::vector<double> values; // the current list of values
std::vector<OP_CODE> optype; // the list of arith operators
double curr_value = 0.0;
int extra_priority = 0;
for( unsigned ii = 0; ii < aExp.size(); ii++ )
{
AM_PARAM_EVAL& prm = aExp[ii];
if( prm.IsOperator() )
{
if( prm.GetOperator() == OPEN_PAR )
{
extra_priority += AM_PARAM_EVAL::GetPriority( OPEN_PAR );
}
else if( prm.GetOperator() == CLOSE_PAR )
{
extra_priority -= AM_PARAM_EVAL::GetPriority( CLOSE_PAR );
}
else
{
optype.emplace_back( prm );
optype.back().m_Priority += extra_priority;
}
}
else // we have a value:
{
values.push_back( prm.GetValue() );
if( optype.size() < 2 )
continue;
OP_CODE& previous_optype = optype[optype.size() - 2];
if( optype.back().m_Priority > previous_optype.m_Priority )
{
double op1 = 0.0;
double op2 = values.back();
values.pop_back();
if( values.size() )
{
op1 = values.back();
values.pop_back();
}
switch( optype.back().m_Optype )
{
case ADD:
values.push_back( op1+op2 );
break;
case SUB:
values.push_back( op1-op2 );
break;
case MUL:
values.push_back( op1*op2 );
break;
case DIV:
values.push_back( op1/op2 );
break;
default:
break;
}
optype.pop_back();
}
}
}
// Now all operators have the same priority, or those having the higher priority
// are before others, calculate the final result by combining initial values and/or
// replaced values.
if( values.size() > optype.size() )
// If there are n values, the number of operator is n-1 or n if the first
// item of the expression to evaluate is + or - (like -$1/2)
// If the number of operator is n-1 the first value is just copied to result
optype.insert( optype.begin(), OP_CODE( POPVALUE ) );
wxASSERT( values.size() == optype.size() );
for( unsigned idx = 0; idx < values.size(); idx++ )
{
curr_value = values[idx];
switch( optype[idx].m_Optype )
{
case POPVALUE:
result = curr_value;
break;
case ADD:
result += curr_value;
break;
case SUB:
result -= curr_value;
break;
case MUL:
result *= curr_value;
break;
case DIV:
result /= curr_value;
break;
default:
break;
}
}
return result;
}
|