inference-engine/src/vpu/graph_transformer/src/utils/simple_math.cpp

   1 // Copyright (C) 2018-2019 Intel Corporation
   2 // SPDX-License-Identifier: Apache-2.0
   3 //
   4
   5 #include <vpu/utils/simple_math.hpp>
   6
   7 #include <cctype>
   8
   9 #include <string>
  10 #include <set>
  11 #include <stack>
  12 #include <map>
  13 #include <stdexcept>
  14 #include <utility>
  15 #include <functional>
  16
  17 #include <vpu/utils/extra.hpp>
  18
  19 namespace vpu {
  20
  21 namespace {
  22
  23 const std::set<char> whitespaces = {
  24     ' ',
  25     '\t',
  26 };
  27
  28 // priority, function
  29 using Operator = std::pair<int, std::function<int(int, int)>>;
  30
  31 const std::map<char, Operator> operators = {
  32     { '+', { 0, std::plus<int>() } },
  33     { '-', { 0, std::minus<int>() } },
  34     { '*', { 1, std::multiplies<int>() } },
  35     { '/', { 1, std::divides<int>()  } },
  36     { '%', { 1, std::modulus<int>()  } },
  37 };
  38
  39 }  // namespace
  40
  41 void SimpleMathExpression::parse(const std::string& expression) {
  42     _parsedTokens.clear();
  43
  44     std::stack<char> operatorStack;
  45
  46     // While there are tokens to be read.
  47     for (size_t i = 0; i != expression.length(); i++) {
  48         // Ignore whitespaces;
  49         while (whitespaces.find(expression[i]) != whitespaces.end()) {
  50             i++;
  51         }
  52
  53         // Read a token.
  54         auto curr = expression[i];
  55
  56         // If the token is a number, then push it to the output queue.
  57         if (std::isdigit(curr)) {
  58             size_t len = 0;
  59             auto value = std::stoi(expression.substr(i), &len);
  60
  61             _parsedTokens.emplace_back(Token(Token::Value, value, 0));
  62
  63             i += (len - 1);
  64
  65             continue;
  66         }
  67
  68         // If the token is a variable, then push it's value to the output queue.
  69         if (_vars.find(curr) != _vars.end()) {
  70             _parsedTokens.emplace_back(Token(Token::Value, _vars.at(curr), 0));
  71
  72             continue;
  73         }
  74
  75         // If the token is an operator, then:
  76         if (operators.find(curr) != operators.end()) {
  77             // While there is an operator at the top of the operator stack with
  78             //   greater than or equal to precedence:
  79             //     pop operators from the operator stack, onto the output queue;
  80             while (!operatorStack.empty() &&
  81                    (operators.find(operatorStack.top()) != operators.end()) &&
  82                    (operators.at(operatorStack.top()).first >= operators.at(curr).first)) {
  83                 auto op = operatorStack.top();
  84                 operatorStack.pop();
  85
  86                 _parsedTokens.emplace_back(Token(Token::Operator, 0, op));
  87             }
  88
  89             //     push the read operator onto the operator stack.
  90             operatorStack.push(curr);
  91
  92             continue;
  93         }
  94
  95         // If the token is a left bracket (i.e. "("), then:
  96         //   push it onto the operator stack.
  97         if (curr == '(') {
  98             operatorStack.push(curr);
  99
 100             continue;
 101         }
 102
 103         // If the token is a right bracket (i.e. ")"), then:
 104         if (curr == ')') {
 105             // While the operator at the top of the operator stack is not a left bracket:
 106             //   pop operators from the operator stack onto the output queue;
 107             while (!operatorStack.empty() &&
 108                    operatorStack.top() != '(') {
 109                 _parsedTokens.emplace_back(Token(Token::Operator, 0, operatorStack.top()));
 110
 111                 operatorStack.pop();
 112             }
 113
 114             //   pop the left bracket from the stack.
 115             // If the stack runs out without finding a left bracket, then there are mismatched parentheses.
 116             if (!operatorStack.empty() &&
 117                 operatorStack.top() == '(') {
 118                 operatorStack.pop();
 119             } else {
 120                 VPU_THROW_EXCEPTION << "Mismatched parentheses in " << expression;
 121             }
 122
 123             continue;
 124         }
 125
 126         // Unknown token
 127         VPU_THROW_EXCEPTION << "Unknown token " << curr << " in " << expression;
 128     }
 129
 130     // If there are no more tokens to read:
 131     //   while there are still operator tokens on the stack:
 132     //     if the operator token on the top of the stack is a bracket, then
 133     //       there are mismatched parentheses;
 134     //     pop the operator onto the output queue.
 135     while (!operatorStack.empty()) {
 136         if (operatorStack.top() == '(') {
 137             VPU_THROW_EXCEPTION << "Mismatched parentheses in " << expression;
 138         }
 139
 140         _parsedTokens.emplace_back(Token(Token::Operator, 0, operatorStack.top()));
 141
 142         operatorStack.pop();
 143     }
 144 }
 145
 146 int SimpleMathExpression::evaluate() const {
 147     std::stack<int> values;
 148     for (const auto& t : _parsedTokens) {
 149         switch (t.type) {
 150         case Token::Value:
 151             values.push(t.value);
 152             break;
 153         case Token::Operator: {
 154             if (values.size() < 2) {
 155                 VPU_THROW_EXCEPTION << "Illegal expression: not enough values for operator evaluation";
 156             }
 157
 158             // pop last 2 values and apply operand
 159             auto val2 = values.top();
 160             values.pop();
 161
 162             auto val1 = values.top();
 163             values.pop();
 164
 165             values.push(operators.at(t.op).second(val1, val2));
 166
 167             break;
 168         }
 169         default:
 170             VPU_THROW_EXCEPTION << "Illegal expression: unhandled token";
 171         }
 172     }
 173
 174     if (values.size() != 1) {
 175         VPU_THROW_EXCEPTION << "Illegal expression: not enough operators";
 176     }
 177
 178     return values.top();
 179 }
 180
 181 }  // namespace vpu