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