0

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

我编写了这个程序，它似乎大部分都在工作，但是在确定表达式是否有效时遇到了问题。

以下是我已完成的基本步骤：

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

1 回答 1

5

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

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

那应该这样做。

于 2013-11-10T21:32:05.970 回答