usage of functions with RPN form

Question

I'm trying to convert mathematical expressions to RPN and then perform symbolic differentiation on them however I'm stuck with some functions like sin() cos() tan()... ln() sqrt() etc. My expression parser only works for more simple cases, like one from the RPN wiki:

3+4*2/(1-5)^2^3

produces the following:

342*15-23^^/+

However when it comes to a more complex formula, like:

sin(2*x^2+6)-(cos(x)/(1-x))

I can't really create the RPN by hand either. My currently working minimalist solution is again implemented according ot the algorithm defined on the Wiki of Shunting-Yard algorithm.

std::string ParseExpression(const std::string &expr) {
    std::string ops = "-+/*^";

    std::stringstream output;
    std::stack<int> stack;

    typedef std::string::const_iterator StringIterator;
    for (StringIterator TOKEN = expr.cbegin(), END = expr.cend(); TOKEN != END; ++TOKEN) {
        const char c = *TOKEN;
        size_t idx = ops.find(c);
        if (idx != std::string::npos) {
            if (stack.empty()) {
                stack.push(idx);
            }
            else {
                while (!stack.empty()) {
                    int prec2 = stack.top() / 2;
                    int prec1 = idx / 2;

                    if (prec2 > prec1 || (prec2 == prec1 && c != '^')) {
                        output << ops[stack.top()];
                        stack.pop();
                    }
                    else {
                        break;
                    }
                }

                stack.push(idx);
            }
        } else if (c == '(') {
            stack.push(-2);
        } else if (c == ')') {
            while (stack.top() != -2) {
                char op = stack.top();

                stack.pop();

                output << ops[op];
            }

            stack.pop();
        } else {
            output << c;
        }
    }

    while (!stack.empty()) {
        output << ops[stack.top()];
        stack.pop();
    }

    return output.str();
}

How can I actually include trigonometric and other functions in the RPN formula and process them correctly?

Answer 1

You'll want to split this all up into tokens of variable size. So that you can add new operators. This allows for bigger numbers than just 0-9, like 101 for example, and longer operators and variable names.

Use the shunting yard algorithm to create the reverse polish notation except now you have new operators, cos and sin, so you will need to store the tokens differently. But basically you just do the shunting yard on it with the new operators and when you solve, don't take the two from the solve stack, alter the value on the top of the solution stack and don't pop or pop and add the result of the function to the top of the stack.

Once you get the tokens properly separated, and you can specify full text operators like sin and cos. Run it like normal.

Your RPN should look something like:

2 x 2 ^ * 6 + sin x cos 1 x - / -   

You can set all the functions to the same top priority or try lower, but I have had no issues with them being the highest priority and the same.

You can actually have functions that take multiple arguments, you just need to solve it correctly.

But just to make a point, you're missing a good tokenizer to set up the shunting yard algorithm with a good starting stack. You're splitting things into single character tokens. You should be making a pass of the string, creating the tokens you need to pass to the shunting yard algorithm. Basically setting it up first.

Answer 2

RPN works the same for functions (including trigonometrics) as it does for operators. For trigonometrics, there is only a single argument (unlike operators, which generally have two).

Your example

sin(2*x^2+6)-(cos(x)/(1-x))

would become something like

2x2^*6+_sin_x_cos_1x-/-

I put before-and-after underscores around sin and cos functions for clarity.

Taken a little more abstractly, if you think of operators as two-argument functions and trigonometrics as one-argument functions, it may make a little more sense - the function always comes after its arguments and evaluates the preceding args in stack-popping order (last in, first out). Changing the operators to functions (and appending "b" for binary, "u" for unary) would give us what's below. RPN says that for anything with a "b" (two arguments), the preceding two args are evaluated in the function. For functions ending in "u" (one argument), the preceding argument is evaluated.

2x2_powb__multb_6_plusb__sinu_x_cosu_1x_minusb__divb__minusb_