Как правильно проверить правильность моего постфиксного выражения?

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

Я написал программу, и, похоже, она по большей части работает, однако возникают проблемы с определением правильности выражения.

Вот основные шаги, которые я сделал:

  1. Попросите пользователя ввести выражение (хранить в виде строки)
  2. Перебрать каждый символ и определить, является ли символ операндом, оператором, пробелом или недопустимым символом.
  3. if(char == операнд) поместить в стек
  4. if(char == operator) всплывает дважды и выполняет арифметику, затем помещает результат в стек
  5. Вне цикла, if(!stack.empty()) result == stack.top, stack.pop
  6. иначе неверное выражение

Таким образом, приведенное выше работает хорошо, если стек уже пуст, но если в стеке есть больше операндов, результат просто распечатывается. Это явно неверно, потому что это должно быть недопустимым выражением, если в стеке все еще есть несколько операндов.

Я думал, что мне следует сделать 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;
}

person StartingGroovy    schedule 10.11.2013    source источник
comment
Можно нам код, пожалуйста?   -  person igleyy    schedule 11.11.2013
comment
@igleyy Абсолютно! Я включу свой файл реализации драйвера.   -  person StartingGroovy    schedule 11.11.2013
comment
Не могли бы вы опубликовать весь код, необходимый для компиляции вашего проекта?   -  person igleyy    schedule 11.11.2013
comment
Во время вычисления выражения стек никогда не должен пустовать. Если да -› ошибка. После того, как вы закончите оценку выражения, если в стеке нет ровно одного элемента (например, stack.size() != 1) -> ошибка. Наконец, извлеките вершину стека и верните ее как значение выражения. Если ваш Stack не имеет оператора size(), вы можете сделать это: Если !empty, извлеките потенциальный результат. Затем, если это все еще !empty -› ошибка, иначе верните потенциальный результат как окончательный результат.   -  person Joe Z    schedule 11.11.2013
comment
@JoeZ Спасибо, у меня нет функции size() в моем стеке. Тем не менее, ваше второе предложение - это именно то, что я печатал. Мне просто показалось странным, что проверка операторов if для одного и того же. Если вы опубликуете это как ответ, я отмечу его как правильный. Кроме того, спасибо igleyy за ваше время!   -  person StartingGroovy    schedule 11.11.2013


Ответы (1)


Чтобы проверить ваше выражение, вам нужно проверить несколько условий.

  • Во время проверки выражения стек никогда не должен пустовать. То есть вы не должны получать stack.empty() при передаче аргументов любому оператору.
  • Once you're done evaluating the expression, the stack should have precisely one element on it. You can determine this through the following procedure (assuming your Stack doesn't have a method for returning the current stack depth):
    1. First check to see if the stack is empty. If so: Error.
    2. Затем извлеките вершину стека в качестве потенциального результата. Отложите это.
    3. Теперь снова проверьте, не пуст ли стек. Если он не пуст: Ошибка.
    4. Наконец, если вы дошли до этого места без ошибок, верните потенциальный результат как окончательный.

Это должно сработать.

person Joe Z    schedule 10.11.2013
comment
Спасибо, Джо, это именно то, что мне нужно было знать :) - person StartingGroovy; 11.11.2013