InfixToPostfix.cpp

Go to the documentation of this file.

#include "InfixToPostfix.h"

#include <iostream>

#include "IException.h"
#include "IString.h"

using namespace std;

namespace Isis {
  InfixToPostfix::InfixToPostfix() {
    initialize();
  }

  InfixToPostfix::~InfixToPostfix() {
    uninitialize();
  }

  void InfixToPostfix::initialize() {
    p_operators.push_back(new InfixOperator(7, "^"));
    p_operators.push_back(new InfixOperator(5, "/"));
    p_operators.push_back(new InfixOperator(5, "*"));
    p_operators.push_back(new InfixOperator(3, "<<"));
    p_operators.push_back(new InfixOperator(3, ">>"));
    p_operators.push_back(new InfixOperator(2, "+"));
    p_operators.push_back(new InfixOperator(2, "-"));
    p_operators.push_back(new InfixOperator(1, ">"));
    p_operators.push_back(new InfixOperator(1, "<"));
    p_operators.push_back(new InfixOperator(1, ">="));
    p_operators.push_back(new InfixOperator(1, "<="));
    p_operators.push_back(new InfixOperator(1, "=="));
    p_operators.push_back(new InfixOperator(1, "!="));
    p_operators.push_back(new InfixOperator(-1, "("));

    // This makes multiple argument functions work
    p_operators.push_back(new InfixOperator(-1, ","));

    p_operators.push_back(new InfixFunction("--",     1));
    p_operators.push_back(new InfixFunction("neg",    1));
    p_operators.push_back(new InfixFunction("sqrt",   1));
    p_operators.push_back(new InfixFunction("abs",    1));
    p_operators.push_back(new InfixFunction("sin",    1));
    p_operators.push_back(new InfixFunction("cos",    1));
    p_operators.push_back(new InfixFunction("tan",    1));
    p_operators.push_back(new InfixFunction("csc",    1));
    p_operators.push_back(new InfixFunction("sec",    1));
    p_operators.push_back(new InfixFunction("cot",    1));
    p_operators.push_back(new InfixFunction("asin",   1));
    p_operators.push_back(new InfixFunction("acos",   1));
    p_operators.push_back(new InfixFunction("atan",   1));
    p_operators.push_back(new InfixFunction("atan2",  2));
    p_operators.push_back(new InfixFunction("sinh",   1));
    p_operators.push_back(new InfixFunction("cosh",   1));
    p_operators.push_back(new InfixFunction("tanh",   1));
    p_operators.push_back(new InfixFunction("asinh",  1));
    p_operators.push_back(new InfixFunction("acosh",  1));
    p_operators.push_back(new InfixFunction("atanh",  1));
    p_operators.push_back(new InfixFunction("log",    1));
    p_operators.push_back(new InfixFunction("log10",  1));
    p_operators.push_back(new InfixFunction("ln",     1));
    p_operators.push_back(new InfixFunction("degs",    1));
    p_operators.push_back(new InfixFunction("rads",    1));
    p_operators.push_back(new InfixFunction("linemin", 1));
    p_operators.push_back(new InfixFunction("linemax", 1));
    p_operators.push_back(new InfixFunction("min",     2));
    p_operators.push_back(new InfixFunction("max",     2));
    p_operators.push_back(new InfixFunction("line",   0));
    p_operators.push_back(new InfixFunction("sample", 0));
    p_operators.push_back(new InfixFunction("band",   0));
    p_operators.push_back(new InfixFunction("pi",     0));
    p_operators.push_back(new InfixFunction("e",      0));
  }

  void InfixToPostfix::uninitialize() {
    for(int i = 0; i < p_operators.size(); i ++) {
      delete p_operators[i];
    }

    p_operators.clear();
  }

  QString InfixToPostfix::cleanSpaces(QString equation) {
    IString equationIStr = equation;
    IString clean = "";
    while(!equationIStr.empty()) {
      IString data = equationIStr.Token(" ");
      if(data.empty()) {
        continue;
      }

      if(clean.empty()) {
        clean = data;
      }
      else {
        clean += " " + data;
      }
    }

    return clean.ToQt();
  }

  QString InfixToPostfix::convert(const QString &infix) {
    // Prep our equation for the conversion
    IString equation = tokenizeEquation(infix);
    IString postfix = "";

    // The algorithm uses a stack
    std::stack<InfixOperator> theStack;

    // Use this to look for two operands in a row. If we find such,
    //   then we know the infix equation is bogus.
    int numConsecutiveOperands = 0;

    // Use this to look for two operators in a row. If we find such,
    //   then we know the infix equation is bogus.
    int numConsecutiveOperators = 0;

    // We'll use tokens to get through the entire equation, which is space-delimited
    //   because of TokenizeEquation. So continue processing until we're out of tokens
    //   and the string is empty.
    while(!equation.empty()) {

      // There will be no empty tokens, so don't worry about checking for it.
      //   TokenizeEquation cleans excess spaces in it's return value.
      QString data = equation.Token(" ").ToQt();

      if(data.compare("(") == 0) {
        theStack.push(*findOperator(data));
      }
      else if(data.compare(")") == 0) {
        QString postfixQStr = postfix.ToQt();
        closeParenthesis(postfixQStr, theStack);
        postfix = postfixQStr;
      }
      else if(isKnownSymbol(data)) {
        QString postfixQStr = postfix.ToQt();
        addOperator(postfixQStr, *findOperator(data), theStack);
        postfix = postfixQStr;

        if(isFunction(data)) {
          // For a general check, zero single argument functions the
          //   same as an operand.
          if(((InfixFunction *)findOperator(data))->argumentCount() == 0) {
            numConsecutiveOperators = 0;
            numConsecutiveOperands ++;
          }
          else {
            // We have a function with arguments, an operand or function call is expected next
            numConsecutiveOperators = 1;
            numConsecutiveOperands = 0;
          }
        }
        else {
          // We found an operator, not a function, so we expect a number next
          numConsecutiveOperators ++;
          numConsecutiveOperands = 0;
        }
      }
      else {
        try {
          // Make sure this is truly an operand and not an operator by casting it
          toDouble(data);
        }
        catch(IException &) {
          throw IException(IException::User,
                           "The operator '" + data + "' is not recognized.",
                           _FILEINFO_);
        }

        // This was clearly an operand at this point
        numConsecutiveOperators = 0;
        numConsecutiveOperands ++;

        postfix += IString(' ' + data + ' ');
      }

      // If we found consecutive operators or operands, tell the user
      if(numConsecutiveOperators > 1) {
        throw IException(IException::User, "Missing an operand near the operator '" + data + "'.", _FILEINFO_);
      }
      else if(numConsecutiveOperands > 1) {
        throw IException(IException::User, "Missing an operator before " + data + ".", _FILEINFO_);
      }
    }

    while(!theStack.empty()) {
      IString op = theStack.top().outputString();

      // Any opening parentheses here are invalid at this point
      if(op == "(") {
        throw IException(IException::User,
                         "There are too many opening parentheses ('(') in the equation.",
                         _FILEINFO_);
      }

      postfix += ' ' + op + ' ';
      theStack.pop();
    }

    // The , is set to an operator that causes multiple-argument functions to work, but
    //   it needs to be stripped out for postfix. This is the correct way to do it.
    postfix = postfix.Remove(",");

    // Clean spaces just to double check and return our postfix answer
    return cleanSpaces(postfix.ToQt());
  }

  bool InfixToPostfix::isKnownSymbol(QString representation) {
    for(int i = 0; i < p_operators.size(); i++) {
      if(representation.compare(p_operators[i]->inputString()) == 0) {
        return true;
      }
    }

    return false;
  }

  bool InfixToPostfix::isFunction(QString representation) {
    if(isKnownSymbol(representation)) {
      return findOperator(representation)->isFunction();
    }
    else {
      return false;
    }
  }

  void InfixToPostfix::addOperator(QString &postfix, const InfixOperator &op, std::stack<InfixOperator> &theStack) {
    while(!theStack.empty()) {
      InfixOperator top = theStack.top();
      theStack.pop();

      if(top.inputString().compare("(") == 0) {
        theStack.push(top);
        break;
      }

      if(top.precedence() < op.precedence()) {
        theStack.push(top);
        break;
      }
      else {
        postfix += ' ' + top.outputString() + ' ';
      }
    }

    theStack.push(op);
  }

  void InfixToPostfix::closeParenthesis(QString &postfix, std::stack<InfixOperator> &theStack) {
    bool openingFound = false;
    while(!theStack.empty()) {
      InfixOperator op = theStack.top();
      theStack.pop();

      if(op.inputString().compare("(") == 0) {
        openingFound = true;
        break;
      }
      else {
        postfix += ' ' + op.outputString() + ' ';
      }
    }

    if(!openingFound) {
      throw IException(IException::User,
                       "There are too many closing parentheses (')') in the equation.",
                       _FILEINFO_);
    }
  }

  InfixOperator *InfixToPostfix::findOperator(QString representation) {
    for(int i = 0; i < p_operators.size(); i++) {
      if(representation.compare(p_operators[i]->inputString()) == 0) {
        return p_operators[i];
      }
    }

    // Nothing found
    throw IException(IException::User, "The operator '" + representation + "' is not recognized.", _FILEINFO_);
  }

  QString InfixToPostfix::tokenizeEquation(const QString &equation) {
    IString output = "";

    // Insert whitespace, make everything lowercase, and change all braces to
    // parenthesis
    for(int i = 0; i < equation.size(); i++) {
      // Ensure there is whitespace in the equation
      if(!equation[i].isLetterOrNumber() && !equation[i].isSpace() && equation[i] != '.') {
        // Convert all braces to parens
        if(equation[i] == '[' || equation[i] == '{') {
          output += " ( ";
        }
        else if(equation[i] == ']' || equation[i] == '}') {
          output += " ) ";
        }
        // Test for multicharacter operators
        else if(i < equation.size() - 1 && equation[i] == '-' && equation[i+1] == '-') {
          output += " -- ";
          i++;
        }
        else if(i < equation.size() - 1 && equation[i] == '<' && equation[i+1] == '<') {
          output += " << ";
          i++;
        }
        else if(i < equation.size() - 1 && equation[i] == '>' && equation[i+1] == '>') {
          output += " >> ";
          i++;
        }
        else if(i < equation.size() - 1 && equation[i] == '>' && equation[i+1] == '=') {
          output += " >= ";
          i++;
        }
        else if(i < equation.size() - 1 && equation[i] == '<' && equation[i+1] == '=') {
          output += " <= ";
          i++;
        }
        else if(i < equation.size() - 1 && equation[i] == '=' && equation[i+1] == '=') {
          output += " == ";
          i++;
        }
        else if(i < equation.size() - 1 && equation[i] == '!' && equation[i+1] == '=') {
          output += " != ";
          i++;
        }
        // Take care of scientific notiation where the exponent is negative
        else if((i > 1) && equation[i] == '-' && equation[i-1].toLower() == 'e' && equation[i-2].isLetterOrNumber()) {
          output += equation[i].toAscii();
        }
        // Look for negative operator disguised as '-'
        else if(equation[i] == '-') {
          bool isNegative = true;

          // If we run into a '(' or the beginning, then the '-' must mean '--' really.
          for(int index = i - 1; index >= 0; index --) {
            if(equation[index] == ' ') {
              continue;
            }

            if(equation[index] != '(' && equation[index] != '/' &&
                equation[index] != '*' && equation[index] != '+') {
              isNegative = false;
              break;
            }

            break;
          }

          if(isNegative) {
            output += " -- ";
          }
          else {
            output += " - ";
          }
        }
        else {
          output += ' ';
          output += equation[i].toAscii();
          output += ' ';
        }
      }
      else {
        output += equation[i].toAscii();
      }
    }

    QString cleanedEquation = cleanSpaces(formatFunctionCalls(output.DownCase().ToQt()));

    return cleanedEquation;
  }

  QString InfixToPostfix::formatFunctionCalls(QString equation) {
    // Clean our space-delimited equation
    equation = cleanSpaces(equation);
    QString output = "";

    // We'll use tokens to get through the entire equation, which is space-delimited.
    //   So continue processing until we're out of tokens and the string is empty.
    while(!equation.isEmpty()) {
      IString tmp = equation;

      QString element = tmp.Token(" ").ToQt();
      equation = tmp.ToQt();

      // Did we find a function? Figure out what it is!
      if(isFunction(element)) {
        // Point to the function. We know if IsFunction returned true,
        //   the result is really a InfixFunction*
        InfixFunction *func = (InfixFunction *)findOperator(element);

        // We want to wrap the entire thing in parentheses, and it's argument string.
        //   So sin(.5)^2 becomes (sin(.5))^2
        output += " ( " + func->inputString() + " (";

        // Deal with 0-argument functions
        if(func->argumentCount() == 0) {
          IString tmp = equation;
          QString next = tmp.Token(" ").ToQt();
          equation = tmp.ToQt();

          // If they didn't add parentheses around the zero-argument
          //   function, we still know what they mean. Close the arguments
          //   and the wrapping parentheses.
          if(next != "(") {
            output += " ) ) ";

            // Step back, we did too much
            equation = next + " " + equation;
          }
          else {
            IString tmp = equation;
            // We see a zero-arg function, and we grabbed an open parenthesis from it.
            //   Make sure the next thing is a close or we have a problem.
            if(tmp.Token(" ") != ")") {
              throw IException(IException::User,
                               "The function " + func->inputString() + " should not have any arguments.",
                               _FILEINFO_);
            }
            equation = tmp.ToQt();

            // Close the arguments and the wrapping parentheses. They wrote their call correct :)
            output += " ) ) ";
          }
        }
        else {
          // Deal with 1+ argument functions by parsing out the arguments

          IString tmp = equation;

          // Make sure the user put parentheses around these, otherwise we're left in the dark.
          if (func->argumentCount() > 1 && tmp.Token(" ") != "(") {
            throw IException(IException::User,
                             "Missing parenthesis after " + func->inputString(),
                             _FILEINFO_);
          }

          equation = tmp.ToQt();

          // Single argument missing parenthesis?
          if(func->argumentCount() == 1) {

            IString tmp = equation;
            QString argument = tmp.Token(" ").ToQt();
            equation = tmp.ToQt();

            if(argument != "(") {
              // We might have a problem. They're calling a function without adding parentheses....
              //   unless it's a negate, because we insert those, tell them their mistake. It's not
              //   my job to figure out what they mean!
              if(func->inputString() != "--") {
                throw IException(IException::User,
                                 "Missing parenthesis after " + func->inputString(),
                                 _FILEINFO_);
              }

              // It's a negate without parentheses, so they mean the next term?
              if(!isFunction(argument)) {
                // If it isn't a function, it's safe to just append
                output += " " + formatFunctionCalls(argument) + " ) ) ";
                continue;
              }
              else {
                // We are negating a function result. We must do a mini-parse to figure out
                //   the function and resursively call, then append the negation.
                QString functionName = argument;

                IString tmp = equation;
                QString openParen = tmp.Token(" ").ToQt();
                equation = tmp.ToQt();

                // No open parens? Call ourself again with this supposed function
                if(openParen != "(") {
                  output += " " + formatFunctionCalls(functionName) + " ) ) ";
                  equation = openParen + " " + equation;
                  continue;
                }
                else {
                  functionName += " (";
                }

                // Parse out our equation quickly, call ourself with it to properly handle it,
                //   and append the negation.
                int numParens = 0;
                while(numParens > -1) {
                  IString tmp = equation;
                  QString newElem = tmp.Token(" ").ToQt();
                  equation = tmp.ToQt();

                  if(newElem == "") {
                    throw IException(IException::User,
                                     "Missing closing parentheses after '" + argument + "'.",
                                     _FILEINFO_);
                  }

                  if(newElem == "(") numParens++;
                  else if(newElem == ")") numParens--;

                  functionName += " " + newElem;
                }

                output += " " + formatFunctionCalls(functionName) + " ) ) ";
                continue;
              }
            }
          }

          QString argument = "";
          int numParens = 0;
          int argNum = 0;
          while(argNum < func->argumentCount()) {
            IString tmp = equation;
            QString elem = tmp.Token(" ").ToQt();
            equation = tmp.ToQt();

            // Ran out of data, the function call is not complete.
            if(elem == "") {
              throw IException(IException::User,
                               "The definition of '" + func->inputString() + "' is not complete.",
                               _FILEINFO_);
            }

            if(elem == "(") {
              numParens ++;
              argument += " (";
            }
            else if(elem == ")") {
              numParens --;

              // Ignore last close, it's not part of the argument and will be added later
              if(numParens != -1) {
                argument += " )";
              }
            }
            else if(elem == "," && numParens == 0) {
              checkArgument(func->inputString(), argNum, argument);
              argument = formatFunctionCalls(argument);
              output += " ( " + argument + " ) , ";
              argNum++;
              argument = "";

              // Too many arguments? We don't expect a comma delimiter on the last argument.
              if(argNum == func->argumentCount()) {
                throw IException(IException::User,
                                 "There were too many arguments supplied to the function '" + func->inputString() + "'.",
                                 _FILEINFO_);
              }
            }
            else {
              argument += " " + elem;
            }

            if(argNum == func->argumentCount() - 1 && numParens == -1) {
              checkArgument(func->inputString(), argNum, argument);
              argument = formatFunctionCalls(argument);
              // close function call & function wrap
              output += " " + argument + " ) ) ";
              argNum++;
              argument = "";
            }
            // Closed the function early?
            else if(numParens == -1) {
              throw IException(IException::User,
                               "There were not enough arguments supplied to the function '" + func->inputString() + "'.",
                               _FILEINFO_);
            }
          }
        }
      }
      // Not a function, preserve & ignore
      else {
        output = output + " " + element;
      }
    }

    return output;
  }

  void InfixToPostfix::checkArgument(QString funcName, int argNum, QString argument) {
    argument = argument.remove(QRegExp("[ ()]"));

    if(argument == "") {
      throw IException(IException::User,
                       "Argument " + toString(argNum + 1) + " in function " + funcName + " must not be empty.",
                       _FILEINFO_);
    }
  }
}