c++ - 在 C++ 后缀上测试太多操作数以中缀堆栈

Question

我目前正在尝试测试操作数是否过多，但无法确定后缀表达式操作数过多时的条件。

有人可以给我一些关于要测试什么的指示吗？

到目前为止，这是我的功能:

void evaluatePostFix(string str){
    Stack stack;
    // Strip whitespaces
    str.erase(str.find(' '), 1);
    if (str.length() == 1 || str.length() == 0){
        string singleOperand;
        singleOperand.push_back(str[0]);
        stack.push(createExpression("", singleOperand, ""));
    }
    int count = 0;

    for (const char & c : str){
        count++;
        if (isOperand(c)){
            string singleOperand;
            singleOperand.push_back(c);
            stack.push(singleOperand);
        } else {
            if (stack.isEmpty()){
                cout << "To many operators" << endl;
                return;
            }
            string operand1 = stack.top();
            stack.pop();
            if (stack.isEmpty()){
                cout << "To many operators" << endl;
                return;
            }
            string operand2 = stack.top();
            stack.pop();
            string operator1, expression;
            operator1.push_back(c);
            expression = createExpression(operand1, operand2, operator1);
            stack.push(expression);
        }
    }
    stack.print();
}

Answer 1

我觉得你想多了。要评估后缀表示法，您可以执行以下操作:

1. 设置堆栈

2. 遍历您的输入

3. 如果找到一个操作数，将其压入堆栈

4. 如果您找到一个操作，将执行该操作所需的操作数从堆栈中弹出。应用操作，然后将结果推回堆栈。如果您无法弹出正确数量的操作数，则说明操作数太少。

5. 在此过程结束时，您的堆栈中应该还剩下一项 - 结果。如果有多个项目，那么在某些时候你有太多的操作数。

这里有一个可读的 python 实现来说明:

def evaluate_postfix(inputstr):

    # split into a list of parts consisting of operands and operators
    ops = inputstr.split()
    stack = []

    for i in ops:

        # if it's an operand push to the stack
        if i.isdigit():
            stack.append(int(i))
        else:
            # if there's not enough operands exit
            if len(stack) < 2:
                print("TOO FEW OPERANDS")
                exit()
            else:
                # pop the operands, apply the operation, and push the result
                a, b = stack.pop(), stack.pop()

                if i == '+': stack.append(a + b)
                elif i == '-': stack.append(a - b)
                elif i == '/': stack.append(a / b)
                else: stack.append(a * b)

    # if there are multiple values left in the stack then at some point
    # there were too many operands for the number of operations
    if len(stack) != 1:
        print("TOO MANY OPERANDS")
        exit()
    return stack[0]

和一些测试用例:

print(evaluate_postfix("1 2 + 3 *"))
# 9
print(evaluate_postfix("1 2 + 3 * *"))
# TOO FEW OPERANDS
print(evaluate_postfix("1 2 3 4 + +"))
# TOO MANY OPERANDS