Parse through String for doubles C++

Question

I've been messing around with Algorithm's and a book that I read mentioned Dijkstra's Two Stack Algorithm to evaluate simple mathematical expressions. The book I read the algorithm in had examples all written in Java, and I was trying to create my own two stack algorithm in C++ (A quick refresher in case anyone forgot).

Two Stack Algorithm:

• Value - Push onto value stack
• Operator - Push onto operator stack
• Left Parenthesis - Ignore
• Right Parenthesis - Pop two values from value stack and one value from operator stack and push the result

So imagine that a user inputs this string into the program:

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

I can't seem to figure out is how I can get C++ to parse through the string while reading the "1" into the vals stack and "+" into the ops stack. How can I go through a string and recognize the doubles from my string, and separate it from the operators that the user inputted?

If anybody wants the example code:

public static void main (String[] args)
{
    Stack<String> ops = new Stack<String>();
    Stack<Double> vals = new Stack<Double>();
    while(!StdIn.isEmpty()){
        String s = StdIn.readString();
        if(s.equals("("))           ;
        else if(s.equals("+"))      ops.push(s);
        else if(s.equals("*"))      ops.push(s);
        else if(s.equals(")")){
            String op = ops.pop();
            if(op.equals("+"))      vals.push(vals.pop()+vals.pop());
            else if(op.equals("*")) vals.push(vals.pop()*vals.pop());
        }
        else vals.push(Double.parseDouble(s));
    }
    StdOut.println(vals.pop());
}

Any help is appreciated!

Answer 1

One way to do this is to use a istringstream. These have the interesting property that if a read fails, it will predictably cause the stream to enter a fail state that you can then recover from. The basic idea will be the following:

• Try to read a double.
• If you can, great!
• If not, clear the failure and read the next token.

Here's an example:

std::istringstream scanner(/* ... input ... */);
while (true) {
    double number;
    scanner >> number;

    if (scanner.fail() && scanner.eof()) {
        break;
    } else if (!scanner.fail()) {
       /* Read a double */
    } else {
       scanner.clear();
       char token;
       scanner >> token;

       /* This skips whitespace; process your token! */
    }
}

Hope this helps!