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

Question

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

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

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

代码：

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()。
• 计算完表达式后，堆栈上应该正好有一个元素。您可以通过以下过程确定这一点（假设堆栈没有返回当前堆栈深度的方法）：
  1. 首先检查堆栈是否为空。如果是：错误。
  2. 接下来，弹出堆栈顶部作为潜在结果。把它放在一边。
  3. 现在，再次检查堆栈是否为空。如果不为空：错误。
  4. 最后，如果您到达这里没有错误，则返回潜在的结果作为最终结果。

应该就行了。