source/booleanevaluator.cpp

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