平常我们写的算术表达式：(3 + 4) * 5，运算顺序是：

1. 先计算括号内的表达式，即(3+4)，运算结果为7；
2. 计算7 * 5，结果为35；

如果先写操作数，再写操作符，这个表达方式叫逆波兰表达式。上面的例子改写为逆波兰表达式为：3 4 + 5 *。要计算这样的表达式，先将+应用在3和4，得到7，然后化简7 5 *，为35。

对于复杂的表达式，这会更加复杂，例如3 4 5 + *表示计算4 5 +（得到9），然后计算3 9 *，最终结果为27。

逆波兰表达式的算法如下：

If you read a number:
    Push it on the stack;
Else if you read an operator:
    Pop 2 values off the stack;
    Combine the values with the opeator;
    Push the result back onto the stack;
Else if there is no more input:
    Pop and display the result;

计算过程图如下：

Cpp 代码实现

#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
static std::vector<std::string> split_string(std::string &input,
                                             char delimeter) {
    std::istringstream in(input); // turn string into input stream
    std::string tmp;
    std::vector<std::string> symbol_list;
    while (std::getline(in, tmp, ' ')) {
        symbol_list.push_back(tmp);
    }
    return symbol_list;
}
double reverse_polish_expression(std::string &input) {
    if (input.empty()) {
        std::fprintf(stderr, "EMPTY INPUT!\n");
        return 0;
    }
    // Split symbols by white space
    std::vector<std::string> symbol_list = split_string(input, ' ');
    std::stack<double> results;
    for (auto i : symbol_list) {
        char ch = *(i.c_str());
        if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            // If the command is an operator,
            // pop the arguments and push the result
            if (results.size() < 2) {
                std::fprintf(stderr, "Insufficient arguments ");
                return 0;
            }
            // Note that the second argument is on the top of stack
            double arg2 = results.top();
            results.pop();
            double arg1 = results.top();
            results.pop();
            if (ch == '+') {
                results.push(arg1 + arg2);
            } else if (ch == '-') {
                results.push(arg1 - arg2);
            } else if (ch == '*') {
                results.push(arg1 * arg2);
            } else {
                if (arg2 == 0) {
                    std::fprintf(stderr, "divisior cannt not be zero! ");
                    return 0;
                }
                results.push(arg1 / arg2);
            }
        } else {
            // Not an operator --> push the input value
            if (ch == ' ') {
                continue;
            }
            results.push(std::stof(i));
        }
    }
    return results.top();
}
int main(int argc, char *argv[]) {
    std::string input;
    input = "3 4 + 5 *"; // output: 35
    std::cout << reverse_polish_expression(input) << std::endl;
    input = "3 4 5 + *"; // output: 27
    std::cout << reverse_polish_expression(input) << std::endl;
    input = "9 2 /"; // output: 4.5
    std::cout << reverse_polish_expression(input) << std::endl;
    input = "90 2 /"; // output: 45
    std::cout << reverse_polish_expression(input) << std::endl;
    input = "9 0 /"; // output: divisior cannt not be zero!
    std::cout << reverse_polish_expression(input) << std::endl;
    input = "3 5 + *"; // output: Insufficient arguments
    std::cout << reverse_polish_expression(input) << std::endl;
    return 0;
}