Hey guys, I’m trying to implement a solution to the RPNEVAL problem. I’m using C++14 with Clang, and my code is as follows (commented and with explanation afterward):
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
std::vector<std::string> parseExpression(const std::string& expression) {
// Turn space-separated expression into vector
std::vector<std::string> expressionArray;
std::istringstream expressionParser(expression);
for (std::string value; std::getline(expressionParser, value, ' ');) {
expressionArray.push_back(value);
}
return expressionArray;
}
std::pair<double, double> popOperands(std::vector<double>& stack) {
// Remove top two elements from stack
if (stack.size() < 2) {
throw "ERROR";
}
auto right = stack.back();
stack.pop_back();
auto left = stack.back();
stack.pop_back();
return std::make_pair(left, right);
}
double evaluatePostfixExpression(const std::vector<std::string>& expression) {
std::vector<double> stack;
stack.reserve(expression.size());
for (const auto& value : expression) {
if (value == "+") {
auto operands = popOperands(stack);
stack.push_back(operands.first + operands.second);
} else if (value == "-") {
auto operands = popOperands(stack);
stack.push_back(operands.first - operands.second);
} else if (value == "*") {
auto operands = popOperands(stack);
stack.push_back(operands.first * operands.second);
} else if (value == "/") {
auto operands = popOperands(stack);
// Divison by 0
if (operands.second == 0) {
throw "ERROR";
}
stack.push_back(operands.first / operands.second);
} else {
// Convert character to integer (automatically cast to double)
stack.push_back(std::stof(value));
}
}
if (!(stack.size() == 1)) {
throw "ERROR";
}
return stack.back();
}
int main() {
for (std::string expression; std::getline(std::cin, expression);) {
try {
std::cout << std::fixed << std::setprecision(4)
<< evaluatePostfixExpression(parseExpression(expression))
<< '\n';
} catch (const char* error) {
// Catch all errors
std::cout << error << '\n';
}
}
}
Explanation:
The main function reads in each expression using getline
, and converts it to a vector using parseExpression
. This parsed expression is then evaluated in evaluatePostfixExpression
using a standard stack based approach. All errors are handled using exceptions propagated to the main function. I’ve tested this code out with the following inputs:
1 2 3 /
2 3 /
3 4 * /
1 2 4 + - 5 * 7 /
5 4 /
7 8 9 / *
4
32840.8434390434847 3384893.492343724339 /
5 0 /
And these are the outputs I get:
ERROR
0.6667
ERROR
-3.5714
1.2500
6.2222
4.0000
0.0097
ERROR
As far as I can tell, these values are correct.
It also looks to me as if I’ve covered all extraneous cases (only one value on stack but no operations, extra leftovers on stack, division by zero, not enough numbers, decimals). However, when I submit this code to SPOJ, I get a SIGABRT error.
I have no idea why this is happening even though it seems my code covers all relevant test cases. I am wondering whether I missed something since the problem specification is somewhat vague.
One thing I did notice is that if I slightly change my output (say one of the error strings is ERROR!
instead of ERROR
), I notice I get an incorrect answer error instead of SIGABRT. Maybe this means something?
What am I doing wrong?