source/booleanevaluator.cpp

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