如何正确测试我的后缀表达式是否有效？

Question

我被分配到编写一个使用堆栈计算后缀表达式的程序。

我编写了该程序，它似乎在大部分情况下都能正常工作，但是在确定表达式是否有效时遇到了问题。

以下是我所做的基本步骤：

1. 要求用户输入表达式（存储为字符串）
2. 遍历每个字符并确定该字符是操作数、运算符、空格还是无效字符
3. if(char == 操作数) 压入堆栈
4. if(char == operator) 弹出两次并进行算术运算，然后将结果压入堆栈
5. 在循环之外， if(!stack.empty()) 结果 == stack.top, stack.pop
6. else 无效表达式

因此，如果堆栈已经是空的，那么上面的方法效果很好，但是如果堆栈上有更多的操作数，结果就会简单地打印出来。这显然是不正确的，因为如果堆栈上还有多个操作数，它应该是一个无效的表达式。

我在想我应该做一个while(!stack.empty()) result = stack.top, stack.pop()但是，这仍然会有同样的问题。

有人可以告诉我应该如何正确测试它吗？

代码：

int main() 
{
    string expression;
    char response;
    int result = -1;        //result of expression. Initialized to -1
    Stack stack;

    printMenu();

    do {
        cout << "Would you like to enter an expression? (y / n)" << endl;
        cin >> response;
        response = toupper(response);

        switch(response) 
        {
            case 'Y':
                //needed due to new line
                cin.ignore();
                doWork(stack, expression, result);
                break;
            case 'N':
                cout << "Exiting program." << endl;
                break;
            default:
                cout << "Invalid response. Try again." << endl;
        }

    } while(response != 'N');

    return EXIT_SUCCESS;
}

doWork（别担心，它会被重命名）函数：

void doWork(Stack stack, string expression, int result)
{
    cout << "Enter a PostFix expression: ";
    getline(cin, expression);

    for(int i = 0; i < expression.size(); i++)
    {
        if(expression[i] == ' ') {
            //do nothing
        } else if(isInteger(expression[i])) {
           stack.push(convertChar2Int(expression[i]));
        } else if(isOperator(expression[i])) {
           // pop last 2 ints from stack and do arithmetic on them 
           int a = stack.top();
           stack.pop();
           int b = stack.top();
           stack.pop();
           // push result onto stack 
           stack.push(calculate(a, b, expression[i]));
        } else {
           //cerr : enter different expression
           cout << expression[i] << " is an invalid character." << endl;
        }
    }

    //the result should be the top of stack
    // THIS IS WHERE MY ISSUE IS
    if(!stack.empty()) {
        result = stack.top();
        stack.pop();
    } else {
        cout << "Invalid expression." << endl;
    }

    cout << "Result: " << result << endl;
}

Answer 1

要验证您的表达式，您需要测试多个条件。

• 在表达式验证期间，堆栈不应为空。也就是说，stack.empty()在向任何运算符弹出参数时不应该得到。
• 完成表达式的计算后，堆栈上应该正好有一个元素。您可以通过以下过程确定这一点（假设您Stack没有返回当前堆栈深度的方法）：
  1. 首先检查堆栈是否为空。如果是这样：错误。
  2. 接下来，弹出堆栈顶部作为您的潜在结果。把它放在一边。
  3. 现在，再次检查堆栈是否为空。如果它不为空：错误。
  4. 最后，如果您没有错误地到达这里，请将潜在结果作为最终结果返回。

那应该这样做。