ACM ICPC - 2168 - Convert

# Problem Info

Type: Regional
Continent: Africa and Arab
Year: 2000

# Problem Statement

The importance of postfix and prefix notation in parsing arithmetic expressions is that these notations are completely free of parentheses. Consequently, an expression in postfix (or prefix) form is crucial because having a unique form for an expression greatly simplifies its evaluation. But we humans prefer to read and evaluate an infix expression especially when it is parenthesized.
We would like to try the conversion from the postfix format to the parenthesized infix format for expression written in some functional language. The language will consist of the unary function INV and the binary functions ADD and MUL.

# Explanation

The solution for this problem is an ad-hoc solution.

Using a stack to store the operands until an operator is found. When this happens, we pop from the stack as many operands as needed for the operator and their order will be in reverse as they were popped. We create the new string for the operation and push it as an operand for the next operation.

As we know that they are all valid operations, we don't need to check for any errors (missing operands, not enough operator for the operands, etc) and when we don't have more operands/operators to process then we just pop the only element in the stack and that will be the whole operation in infix syntax.

# Code

The C++ that solves the problem is the following(2168.cpp):

#include <iostream>
#include <sstream>
#include <string>
#include <cctype>
#include <deque>

using namespace std;

int main() {

string word;
char line[1000];
int n;

cin >> n;
cin.getline(line, 1000);
for (int i = 0; i < n; ++i) {
cin.getline(line, 1000);
string str_line(line);
istringstream sline(str_line, istringstream::in);
deque<string> stack;
while (sline >> word) {
if (isalpha(word[0])) { // Operator
switch(toupper(word[0])) {
case 'I':
word = "Inv";
break;
case 'M':
word = "Mul";
break;
case 'A':
break;
}
string first_operand;
string to_push(word);
string second_operand;

if (word != "Inv") {
second_operand = stack.back();
stack.pop_back();
}
first_operand = stack.back();
stack.pop_back();

to_push += " (";
if (isalpha(first_operand[0])) {
to_push += " ";
}
to_push += first_operand;
if (word != "Inv") {
to_push += ", ";
to_push += second_operand;
}
to_push += ")";
stack.push_back(to_push);
}
else { // Operand
stack.push_back(word);
}
}
cout << stack.back() << '\n';

}

return 0;
}