c++ - C++中的两个堆栈算法

Question

这里是编码新手，我一直在询问我应该如何在 C++ 中创建用于计算简单表达式的双堆栈算法(Dijkstra 的双堆栈算法)。为任何需要它的人快速复习:

双栈算法:

• 值(value) - 插入值(value)堆栈
• 运算符 - 压入运算符堆栈
• 左括号 - 忽略
• 右括号 - 从值栈中弹出两个值，从运算符栈中弹出一个值并压入结果

似乎使用向我推荐的 istringstream 应该允许我将用户输入的表达式分为基本表达式、 double 表达式和非 double 表达式。这应该允许我分别填充我的 vals 和 ops 堆栈，但是在调试时，我意识到我的 vals 堆栈最后是空的(导致段错误)

我不知道自己做错了什么，如有任何帮助，我们将不胜感激!请记住，我是编码方面的新手，我的语法可能很糟糕，因此欢迎任何类型的批评。

引用输入:

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

应该输出:

101

到目前为止，我的代码如下所示:

stack<string> ops;
stack<double> vals;
string input;
getline(cin, input);
istringstream scanner(input);
while(true){
    double num;
    scanner >> num;
    if(scanner.fail() && scanner.eof())     break;
    else if(!scanner.fail())                vals.push(num);
    else{
        scanner.clear();
        string token;
        scanner >> token;
        if(token == "(")                    ;
        else if(token == "+")               ops.push(token);
        else if(token == "*")               ops.push(token);
        /*Add more operations here (Log, sin, cos...)*/
        else if(token == ")"){
            string op = ops.top();
            ops.pop();
            if(op == "+"){
                double a, b;
                a = vals.top();
                vals.pop();
                b = vals.top();
                vals.pop();
                vals.push(a+b);
            }
            else if(op == "*"){
                double a, b;
                a = vals.top();
                vals.pop();
                b = vals.top();
                vals.pop();
                vals.push(a*b);
            }
            /*Add more operations here*/
        }
    }
return vals.top();
}

感谢您的帮助!

Answer 1

原来是这个问题:

scanner >> num;
if (scanner.fail() && scanner.eof()) break;
else if (!scanner.fail())             vals.push(num);

将其更改为以下解决了问题:

if (scanner >> num) vals.push(num);
if (scanner.fail() && scanner.eof()) break;
else {
    // ...
}

将 return 语句放在循环下面也有帮助。

Live example