surfaces/conv/shunt.h

0001 /* Copyright (c) 2012 the authors listed at the following URL, and/or
0002 the authors of referenced articles or incorporated external code:
0003 http://en.literateprograms.org/Shunting_yard_algorithm_(C)?action=history&offset=20080201043325
0004
0005 Permission is hereby granted, free of charge, to any person obtaining
0006 a copy of this software and associated documentation files (the
0007 "Software"), to deal in the Software without restriction, including
0008 without limitation the rights to use, copy, modify, merge, publish,
0009 distribute, sublicense, and/or sell copies of the Software, and to
0010 permit persons to whom the Software is furnished to do so, subject to
0011 the following conditions:
0012
0013 The above copyright notice and this permission notice shall be
0014 included in all copies or substantial portions of the Software.
0015
0016 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
0017 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
0018 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
0019 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
0020 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
0021 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
0022 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
0023
0024 Retrieved from: http://en.literateprograms.org/Shunting_yard_algorithm_(C)?oldid=12454
0025 */
0026
0027 #include <stdlib.h>
0028 #include <stdio.h>
0029 #include <ctype.h>
0030
0031 #define SHUNT_MAXOPSTACK 256
0032 #define SHUNT_MAXNUMSTACK 256
0033
0034 namespace shunt {
0035
0036 bool eval_not(bool a1, bool a2) { return !a1; }
0037 bool eval_and(bool a1, bool a2) { return a1 && a2; }
0038 bool eval_or(bool a1, bool a2) { return a1 || a2; }
0039
0040 enum { ASSOC_NONE = 0, ASSOC_LEFT, ASSOC_RIGHT };
0041
0042 struct op_s {
0043   char op;
0044   int prec;
0045   int assoc;
0046   int unary;
0047   bool (*eval)(bool a1, bool a2);
0048 } ops[] = {{'!', 10, ASSOC_RIGHT, 1, eval_not},
0049            {'&', 8, ASSOC_LEFT, 0, eval_and},
0050            {'|', 5, ASSOC_LEFT, 0, eval_or},
0051            {'(', 0, ASSOC_NONE, 0, NULL},
0052            {')', 0, ASSOC_NONE, 0, NULL}};
0053
0054 struct op_s *getop(char ch)
0055 {
0056   size_t i;
0057   for (i = 0; i < sizeof ops / sizeof ops[0]; ++i) {
0058     if (ops[i].op == ch) return ops + i;
0059   }
0060   return nullptr;
0061 }
0062
0063 void push_opstack(struct op_s *op, struct op_s **opstack, int &nopstack)
0064 {
0065   if (nopstack > SHUNT_MAXOPSTACK - 1) {
0066     fprintf(stderr, "ERROR: Operator stack overflow\n");
0067     exit(EXIT_FAILURE);
0068   }
0069   opstack[nopstack++] = op;
0070 }
0071
0072 struct op_s *pop_opstack(struct op_s **opstack, int &nopstack)
0073 {
0074   if (!nopstack) {
0075     fprintf(stderr, "ERROR: Operator stack empty\n");
0076     exit(EXIT_FAILURE);
0077   }
0078   return opstack[--nopstack];
0079 }
0080
0081 void push_numstack(bool num, bool *numstack, int &nnumstack)
0082 {
0083   if (nnumstack > SHUNT_MAXNUMSTACK - 1) {
0084     fprintf(stderr, "ERROR: Number stack overflow\n");
0085     exit(EXIT_FAILURE);
0086   }
0087   numstack[nnumstack++] = num;
0088 }
0089
0090 bool pop_numstack(bool *numstack, int &nnumstack)
0091 {
0092   if (!nnumstack) {
0093     fprintf(stderr, "ERROR: Number stack empty\n");
0094     exit(EXIT_FAILURE);
0095   }
0096   return numstack[--nnumstack];
0097 }
0098
0099 void shunt_op(struct op_s *op, struct op_s **opstack, int &nopstack, bool *numstack, int &nnumstack)
0100 {
0101   struct op_s *pop;
0102   bool n1, n2;
0103   if (op->op == '(') {
0104     push_opstack(op, opstack, nopstack);
0105     return;
0106   } else if (op->op == ')') {
0107     while (nopstack > 0 && opstack[nopstack - 1]->op != '(') {
0108       pop = pop_opstack(opstack, nopstack);
0109       n1  = pop_numstack(numstack, nnumstack);
0110       if (pop->unary)
0111         push_numstack(pop->eval(n1, false), numstack, nnumstack);
0112       else {
0113         n2 = pop_numstack(numstack, nnumstack);
0114         push_numstack(pop->eval(n2, n1), numstack, nnumstack);
0115       }
0116     }
0117     if (!(pop = pop_opstack(opstack, nopstack)) || pop->op != '(') {
0118       fprintf(stderr, "ERROR: Stack error. No matching \'(\'\n");
0119       exit(EXIT_FAILURE);
0120     }
0121     return;
0122   }
0123
0124   if (op->assoc == ASSOC_RIGHT) {
0125     while (nopstack && op->prec < opstack[nopstack - 1]->prec) {
0126       pop = pop_opstack(opstack, nopstack);
0127       n1  = pop_numstack(numstack, nnumstack);
0128       if (pop->unary)
0129         push_numstack(pop->eval(n1, 0), numstack, nnumstack);
0130       else {
0131         n2 = pop_numstack(numstack, nnumstack);
0132         push_numstack(pop->eval(n2, n1), numstack, nnumstack);
0133       }
0134     }
0135   } else {
0136     while (nopstack && op->prec <= opstack[nopstack - 1]->prec) {
0137       pop = pop_opstack(opstack, nopstack);
0138       n1  = pop_numstack(numstack, nnumstack);
0139       if (pop->unary)
0140         push_numstack(pop->eval(n1, 0), numstack, nnumstack);
0141       else {
0142         n2 = pop_numstack(numstack, nnumstack);
0143         push_numstack(pop->eval(n2, n1), numstack, nnumstack);
0144       }
0145     }
0146   }
0147   push_opstack(op, opstack, nopstack);
0148 }
0149
0150 bool logic_evaluate(std::string const &slogic)
0151 {
0152   struct op_s *opstack[SHUNT_MAXOPSTACK];
0153   int nopstack = 0;
0154
0155   bool numstack[SHUNT_MAXNUMSTACK];
0156   int nnumstack       = 0;
0157   auto tstart         = slogic.size();
0158   struct op_s startop = {'X', 0, ASSOC_NONE, 0, NULL}; /* Dummy operator to mark start */
0159   struct op_s *op     = NULL;
0160   int n1, n2;
0161   struct op_s *lastop = &startop;
0162
0163   for (size_t iexpr = 0; iexpr < slogic.size(); ++iexpr) {
0164     if (tstart == slogic.size()) {
0165
0166       if ((op = getop(slogic[iexpr]))) {
0167         if (lastop && (lastop == &startop || lastop->op != ')')) {
0168           if (op->op != '(' && op->op != '!') {
0169             fprintf(stderr, "ERROR: Illegal use of binary operator (%c)\n", op->op);
0170             exit(EXIT_FAILURE);
0171           }
0172         }
0173         shunt_op(op, opstack, nopstack, numstack, nnumstack);
0174         lastop = op;
0175       } else if (isdigit(slogic[iexpr]))
0176         tstart = iexpr;
0177       else if (!isspace(slogic[iexpr])) {
0178         fprintf(stderr, "ERROR: Syntax error\n");
0179         exit(EXIT_FAILURE);
0180       }
0181     } else {
0182       if (isspace(slogic[iexpr])) {
0183         push_numstack(slogic[tstart] - '0', numstack, nnumstack);
0184         tstart = slogic.size();
0185         lastop = nullptr;
0186       } else if ((op = getop(slogic[iexpr]))) {
0187         push_numstack(slogic[tstart] - '0', numstack, nnumstack);
0188         tstart = slogic.size();
0189         shunt_op(op, opstack, nopstack, numstack, nnumstack);
0190         lastop = op;
0191       } else if (!isdigit(slogic[iexpr])) {
0192         fprintf(stderr, "ERROR: Syntax error\n");
0193         exit(EXIT_FAILURE);
0194       }
0195     }
0196   }
0197   if (tstart < slogic.size()) push_numstack(slogic[tstart] - '0', numstack, nnumstack);
0198
0199   while (nopstack) {
0200     op = pop_opstack(opstack, nopstack);
0201     n1 = pop_numstack(numstack, nnumstack);
0202     if (op->unary)
0203       push_numstack(op->eval(n1, 0), numstack, nnumstack);
0204     else {
0205       n2 = pop_numstack(numstack, nnumstack);
0206       push_numstack(op->eval(n2, n1), numstack, nnumstack);
0207     }
0208   }
0209   if (nnumstack != 1) {
0210     fprintf(stderr, "ERROR: Number stack has %d elements after evaluation. Should be 1.\n", nnumstack);
0211     exit(EXIT_FAILURE);
0212   }
0213   //printf("%d\n", numstack[0]);
0214
0215   return numstack[0];
0216 }
0217 } // end namespace shunt