Operate prefixed expression from input

Question

I want to operate expression of the following kind without using stacks, only recursion:

+ - 8 m 4 + 5 7 9

This should equal 4, because −8 + max3(4, 5 + 7, 9), being m a ternary operator that finds the maximum. I know how to crack this kind of operations for a simpler expressions, but however trying to adapt my code for this one is giving me wrong outputs. My code is as follows:

#include <iostream>
#include <algorithm>
#include <initializer_list>
using namespace std;

int operate() {
    char op;
    cin >> op;
    int val = op - '0';
    if (val < 0) {
        if (op == 'm') return std::max({ operate(), operate(), operate() });
        else if (op == '+') return operate() + operate();
        else return - operate();
    }
    return val;
}

int main() {
    cout << operate() << "\n";
}

This outputs 53, when 4 is expected. Any suggestions on making it work and make it less ugly? I want the input to be read from cin.

Answer 1

Any suggestions on making it work and make it less ugly?

Here is a working implementation that's a bit neater:

#include <iostream>
int op(char c = std::cin.get()) {
  switch (c) {
    case 'm': return std::max({op(), op(), op()});
    case '+': return op() + op();
    case '-': return -op();
    default : return std::isspace(c) ? op() : c - '0';
  }
}

As for the code's bug, as Manuel said val < 0 is not an effective comparison. The ASCII values for '+' and '-' are less than '0', but 'm' is not.

Answer 2

When your code gets the minus sign - it substract eight to the next number, which is m (61).

int operate() {
    char op;
    cin >> op;
    int val = op - '0';
    std::cout << "Call with " << val << " " << op << std::endl;
    if (val < 0) {
        std::cout << "In if" << std::endl;
        if (op == 'm') {
            std::cout << "in m" << std::endl;
            return std::max({
                    [](){
                        std::cout << "1" << std::endl;
                        return operate();}(),
                    [](){
                        std::cout << "2" << std::endl;
                        return operate();}(),
                    [](){
                        std::cout << "3" << std::endl;
                        return operate();}() });
        }
        else if (op == '+') {
            std::cout << "in +" << std::endl;
            return [](){
                        std::cout << "4" << std::endl;
                        return operate();}() + [](){
                        std::cout << "5" << std::endl;
                        return operate();}();
        } else {
            std::cout << "in else" << std::endl;
            return - [](){
                        std::cout << "6" << std::endl;
                        return operate();}();
        }
    }
    std::cout << "return " << val << std::endl;
    return val;
}

int main() {
    cout << operate() << "\n";
}

Output:

echo "+ -8 m 4 + 5 7 9" | ./main
Call with -5 +
In if
in +
4
Call with -3 -
In if
in else
6
Call with 8 8
return 8
5
Call with 61 m
return 61
53

You shouldn't check if (val < 0) but isdigit() or isalpha() in the op. When you find m, val isn't negative, so it simply returns the value when you want to process the m operator.

With if (!::isdigit(op)) the output:

Call with -5 +
In if
in +
4
Call with -3 -
In if
in else
6
Call with 8 8
return 8
5
Call with 61 m
In if
in m
1
Call with 4 4
return 4
2
Call with -5 +
In if
in +
4
Call with 5 5
return 5
5
Call with 7 7
return 7
3
Call with 9 9
return 9
4

Which is what you expect.