source/booleanevaluator.cpp

   1 #include <stdexcept>
   2 #include "booleanevaluator.h"
   3
   4 using namespace std;
   5
   6 /* I'd rather have overloads with different slots, but that creates an
   7 ambiguity because slots have template constructors. */
   8 BooleanEvaluator::BooleanEvaluator(const Slot &s, bool allow_compare):
   9         slot(s),
  10         ops(allow_compare ? "&|!=^" : "&|!")
  11 { }
  12
  13 bool BooleanEvaluator::evaluate(const string &str)
  14 {
  15         string buf;
  16         last_was_op = true;
  17         for(string::const_iterator i=str.begin();; ++i)
  18         {
  19                 if(i!=str.end() && (isalnum(*i) || (!buf.empty() && (*i=='_' || *i=='-'))))
  20                         buf += *i;
  21                 else
  22                 {
  23                         if(!buf.empty())
  24                         {
  25                                 if(!last_was_op)
  26                                         throw runtime_error("syntax error at "+buf);
  27
  28                                 char op = (op_stack.empty() ? 0 : op_stack.back());
  29                                 if(op=='=' || op=='^')
  30                                 {
  31                                         op_stack.pop_back();
  32                                         string var = var_stack.back();
  33                                         var_stack.pop_back();
  34                                         bool value = (slot(var, &buf) == (op=='='));
  35                                         value_stack.push_back(value);
  36                                 }
  37                                 else
  38                                         var_stack.push_back(buf);
  39
  40                                 buf.clear();
  41                                 last_was_op = false;
  42                         }
  43
  44                         if(i==str.end())
  45                                 break;
  46                         else if(isspace(*i))
  47                                 ;
  48                         else if(ops.find(*i)!=string::npos)
  49                                 push_op(*i);
  50                         else
  51                                 throw runtime_error("syntax error at "+string(1, *i));
  52                 }
  53         }
  54
  55         collapse(0);
  56
  57         bool value = pop_value();
  58         if(!value_stack.empty())
  59                 throw runtime_error("too many values");
  60
  61         return value;
  62 }
  63
  64 void BooleanEvaluator::push_op(char op)
  65 {
  66         if(last_was_op!=is_unary(op))
  67                 throw runtime_error("syntax error at "+string(1, op));
  68         // TODO Disallow mixing of ! and =/^
  69         if(is_logic(op) && !var_stack.empty())
  70                 value_stack.push_back(pop_value());
  71
  72         if(!is_unary(op))
  73                 collapse(precedence(op));
  74         op_stack.push_back(op);
  75         last_was_op = true;
  76 }
  77
  78 bool BooleanEvaluator::pop_value()
  79 {
  80         if(!var_stack.empty())
  81         {
  82                 string var = var_stack.back();
  83                 var_stack.pop_back();
  84                 return slot(var, 0);
  85         }
  86         else if(!value_stack.empty())
  87         {
  88                 bool value = value_stack.back();
  89                 value_stack.pop_back();
  90                 return value;
  91         }
  92
  93         throw runtime_error("value stack underflow");
  94 }
  95
  96 void BooleanEvaluator::collapse(unsigned until)
  97 {
  98         while(!op_stack.empty())
  99         {
 100                 char op = op_stack.back();
 101                 if(precedence(op)<until)
 102                         return;
 103
 104                 op_stack.pop_back();
 105                 bool value1 = pop_value();
 106                 if(is_unary(op))
 107                 {
 108                         if(op=='!')
 109                                 value1 = !value1;
 110                 }
 111                 else
 112                 {
 113                         bool value2 = pop_value();
 114                         if(op=='&')
 115                                 value1 = (value1 && value2);
 116                         else if(op=='|')
 117                                 value1 = (value1 || value2);
 118                 }
 119                 value_stack.push_back(value1);
 120         }
 121 }
 122
 123 unsigned BooleanEvaluator::precedence(char op)
 124 {
 125         if(op=='&')
 126                 return 1;
 127         else if(op=='=' || op=='^')
 128                 return 2;
 129         else if(op=='!')
 130                 return 3;
 131         else
 132                 return 0;
 133 }
 134
 135 bool BooleanEvaluator::is_unary(char op)
 136 {
 137         return op=='!';
 138 }
 139
 140 bool BooleanEvaluator::is_logic(char op)
 141 {
 142         return (op=='&' || op=='|' || op=='!');
 143 }