Method infixToPostfix

src/Eval.cpp:631–687

/////////////////////////////////////////////////////////////////////////// Dijkstra Shunting Algorithm. https://en.wikipedia.org/wiki/Shunting-yard_algorithm While there are tokens to be read: Read a token. If the token is an operator, o1, then: while there is an operator token, o2, at the top of the stack, and either o1 is left-associative and its precedence is less than or equal to that of o2,

//   Exit.
//
void Eval::infixToPostfix(std::vector<std::pair<std::string, Lexer::Type>>& infix) const {
  // Short circuit.
  if (infix.size() == 1) return;

  // Result.
  std::vector<std::pair<std::string, Lexer::Type>> postfix;

  // Shunting yard.
  std::vector<std::pair<std::string, Lexer::Type>> op_stack;

  // Operator characteristics.
  char type;
  unsigned int precedence;
  char associativity;

  for (auto& token : infix) {
    if (token.second == Lexer::Type::op && token.first == "(") {
      op_stack.push_back(token);
    } else if (token.second == Lexer::Type::op && token.first == ")") {
      while (op_stack.size() && op_stack.back().first != "(") {
        postfix.push_back(op_stack.back());
        op_stack.pop_back();
      }

      if (op_stack.size())
        op_stack.pop_back();
      else
        throw std::string("Mismatched parentheses in expression");
    } else if (token.second == Lexer::Type::op &&
               identifyOperator(token.first, type, precedence, associativity)) {
      char type2;
      unsigned int precedence2;
      char associativity2;
      while (op_stack.size() > 0 &&
             identifyOperator(op_stack.back().first, type2, precedence2, associativity2) &&
             ((associativity == 'l' && precedence <= precedence2) ||
              (associativity == 'r' && precedence < precedence2))) {
        postfix.push_back(op_stack.back());
        op_stack.pop_back();
      }

      op_stack.push_back(token);
    } else {
      postfix.push_back(token);
    }
  }

  while (op_stack.size()) {
    if (op_stack.back().first == "(" || op_stack.back().first == ")")
      throw std::string("Mismatched parentheses in expression");

    postfix.push_back(op_stack.back());
    op_stack.pop_back();
  }

  infix = postfix;
}