Тестирование слишком большого количества операндов в постфиксе C ++ для инфиксного стека - PullRequest
Новая
       70

Тестирование слишком большого количества операндов в постфиксе C ++ для инфиксного стека

2 голосов
/ 12 марта 2019

В настоящее время я пытаюсь проверить, не слишком ли много операндов, но не могу определить условие, когда в выражении постфикса слишком много операндов.

Может ли кто-нибудь дать мне какие-нибудь советы по поводу того, что нужно проверять?

Вот моя функция на данный момент: 

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();
}

1 Ответ

3 голосов
/ 12 марта 2019

Я думаю, вы думаете об этом.Чтобы оценить постфиксную нотацию, выполните следующие действия:

  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
...