---

This is my solution to a problem posted on Spoj.com called “Transform the Expression (ONP)”. The program first takes a number N, which is the number of test cases that will follow. Next, it takes N expressions in Algebraic form, using the following two-argument operators: +, -, *, /, ^ (precedence from lowest to highest) and brackets (). The operands are lowercase letters (a, b, …, z). We are also assuming that there is only one RPG form (no expressions like a * b * c). The output will be N expressions in Reverse Polish Notation, created from the input expressions.

---

Sample Input
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))
Sample Output

abc*+
ab+zx+*
at+bac++cd+^*

---

/******************************************************************************/
/*
  Author:  Alejandro Hitti
  Brief:   Solution for the Spoj.com problem ONP: Transform the Expression.
           Transforms an expresion in algebraic form into Reverse Polish
           Notation (RPN).

  All content (C) 2014-2015 Alejandro Hitti http://alejandrohitti.com.
  All rights reserved.
*/
/******************************************************************************/
#include <string>
#include <iostream>
#include <stack>

/*
 * Checks precedence between operators.
 * Returns true if the first has lower or equal precedence than the second.
 * Returns false if the first has higher precedence than the second.
 */
bool HasPrecedence(char first, char second)
{
  bool result = false;

  switch (first)
  {
    case '+' :
    {
      result = true;
    } break;

    case '-' :
    {
      if (second == '+')
        result = true;
    } break;

    case '*' :
    {
      if (second == '+' || second == '-')
        result = true;
    } break;

    case '/' :
    {
      if (second != '^')
        result = true;
    } break;

    // The ^ operator was skipped because it always returns false

    return result;
  }
}

/*
 * Recursive function that gets called when there are no more operands and
 * operation precedence is being decided for the last remaining operators on
 * the stack.
 */
void LastTest(char current, std::stack<char>& stack, std::string& rpnExpression)
{
  if (HasPrecedence(stack.top(), current))
    stack.push(current);

  else
  {
    rpnExpression += stack.top();
    stack.pop();
    LastTest(current, stack, rpnExpression);
  }
}

/*
 * Takes in an expression as a string and starts evaluating each character,
 * using a stack to keep track of operators and precedences.
 */
void Transform(std::string& algExpression, std::string& rpnExpression)
{
  std::stack<char> stack;

  for (int i = 0; i < algExpression.length(); ++i)
  {
    char current = algExpression[i];

    // Operands get added to the buffer as soon as they are seen
    if (current >= 'a' && current <= 'z')
      rpnExpression += current;

    else if (current == '(')
      stack.push(current);

    // When you find a closing parenthesis, you add the top elements of the
    // stack to the buffer until you find the matching open parenthesis. 
    else if (current == ')')
    {
      while (stack.top() != '(')
      {
        rpnExpression += stack.top();
        stack.pop();
      }

      stack.pop();
    }

    // If the code gets all the way here, it means that the current character
    // is an operator.
    else
    {
      if (stack.empty())
        stack.push(current);

      else if (stack.top() == '(')
        stack.push(current);

      else
        LastTest(current, stack, rpnExpression);
    }
  }

  // Removes the rest of the elements from the stack
  while (!stack.empty())
  {
    std::cout << stack.top();
    stack.pop();
  }
}

/*
 * Entry point of the program. Takes a number N, which indicates the number of
 * test cases to follow. Then transforms every expression and prints them.
 */
int main (void)
{
  int numEntries;
  std::cin >> numEntries;

  std::string algExpression;

  // Storing outputs in a single buffer to ensure that std::cout gets called
  // only once, as it is a very expensive operation.
  std::string rpnExpression = "";

  for (int i = 0; i < numEntries; ++i)
  {
    std::cin >> algExpression;
    Transform(algExpression, rpnExpression);
    rpnExpression += '\n';
  }

  // Print the result to current output.
  std::cout << rpnExpression << std::endl;

  return 0;
}

[top]