Check if a string contains a valid postfix expression

Question

I have a string that needs to be check for a valid postfix expression.
A valid postfix string is 1 2 + but not 1 2+ since each character needs a space. Also, since it's a string, you can enter words, but they should return -1 for this function.

I have tried using vector array with strings and checking for valid ints, but when the user enters letters this obviously creates a problem.

string postfix = "1 2 +"; // valid
string postfix = "soemthing"; // error
string postfix = "1 2+" ; // error since there is no space. 
if (!isdigit(postfix[0]))  
return -1;

int t;
string line = "55 124 4 5";
std::vector <int> ints;
    std::istringstream iss ( line, std::istringstream::in);
    int main() {
            while (iss >> t )
            {
                    ints.push_back(t);
            }

    if (!digit(ints[0]) || !digit(ints[0])) 
    return -1; 


    }

~

Use regex to validate and split the string. The pattern should also be pretty straight forward. Like `"(\d+)\s(\d+)\s(\+)"`. — Timo, May 12 '19 at 23:17

Rik · Accepted Answer · 2019-05-14T03:14:26.077

From this post you can get the algorithm to check. In c++:

int isValid(string postfix) {

    int l = postfix.size();
    char c;
    bool numStarted = false;
    int counter = 0;
    for (int i = 0; i < l; i++) {
        c = postfix.at(i);

        if (numStarted == true && c == ' ') {
            numStarted = false;
        } else if (numStarted == false && c == ' ') {
            return -1;
        } else if (c == '-' || c == '+' || c == '*' || c == '/') {
            if (counter < 2 || numStarted) {
                return -1;
            }
            counter--;
            numStarted = true;
        } else if (!isdigit(c)) {
            return -1;
        } else if (!numStarted && isdigit(c)) {
            counter++;
            numStarted = true;
        }
    }
    return (counter == 1 ? 1 : -1);
}

To test this:

int main(int argc, char** argv) {
    string postfix1 = "1 2 +"; // valid
    string postfix2 = "soemthing"; // error
    string postfix3 = "1 2+"; // error since there is no space.

    cout << isValid(postfix1) << endl;
    cout << isValid(postfix2) << endl;
    cout << isValid(postfix3) << endl;

    return 0;
}

output:

1
-1
-1

That works well, but not for this case: 1 + 2 which is not a valid postfix. — user3605629, May 13 '19 at 06:53
I had to change: if (counter < 1 || numStarted) { to if (counter < 2 || numStarted) { — user3605629, May 13 '19 at 07:02
Rik, anyway you could help me with a Huffman tree? It's my last assignment for the quarter and it's been nothing but stress. — user3605629, May 28 '19 at 02:42

Check if a string contains a valid postfix expression

1 Answers1