Ошибка при переводе выражения в обратную польскую запись

#cpp #алгоритм #польская_запись

Имеется код:

#include 
#include 
using namespace std;
struct stack {
    char info;
    stack* next;
};
void addToStack(char sym, stack *&begin);
void showStack(stack *begin);
int priority(char op);
void showElementsInBrackets(string &output, stack *&begin);
void executeFromStackElements(string &output, stack *&begin);
int main() {
    stack *begin = NULL;
    string input, output = "";
    cin >> input;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] >= 'a' && input[i] <= 'z') {
            output += input[i];
        }
        else if (input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i]
== '/' || input[i] == '%' || input[i] =='(') {
            if (begin == NULL || input[i] == '(') {
                addToStack(input[i], begin);
            }
            else {
                if (priority(begin->info) <= priority(input[i])) {
                    addToStack(input[i], begin);
                }
                else {
                    executeFromStackElements(output, begin);
                    addToStack(input[i], begin);
                }
            }
        }
        else if (input[i] == ')') {
            showElementsInBrackets(output, begin);
        }
    }
    executeFromStackElements(output, begin);
    cout << "Output:" << endl;
    cout << output << endl;
    system("pause");
    return 0;
}

void addToStack(char sym, stack *& begin)
{
    stack *t = new stack;
    t->info = sym;
    t->next = begin;
    begin = t;
}

void showStack(stack * begin)
{
    stack *t = begin;
    while (t != NULL) {
        cout << t->info << endl;
        t = t->next;
    }
}

int priority(char op)
{
    if (op == '(') {
        return 1;
    }
    else if (op == '+' || op == '-') {
        return 2;
    }
    else if (op == '*' || op == '/' || op == '%') {
        return 3;
    }
}



void showElementsInBrackets(string & output, stack *& begin)
{
    while (begin->info != '(' && begin != NULL) {
        output += begin->info;
        begin = begin->next;
    }
    begin = begin->next;
}

void executeFromStackElements(string & output, stack *& begin)
{
    while (begin != NULL) {
        output += begin->info;
        begin = begin->next;
    }
}


Задача - перевод выражения в ОПЗ. Однако при определенном вводе, возникают проблемы
со скобками. Например, при вводе a+bcd+(e-f)(gh+i), возникает 
ошибка 


  Вызвано исключение по адресу 0x010F3CD3 в OPZ.exe: 0xC0000005:
  нарушение прав доступа при чтении по адресу 0x00000000.
  И указывает на строку 


while (begin->info != '(') {


Смотрю по отладке, там выходная строка это abcd**+ef-gh*(*+i+
Как я понимаю, ошибка из-за того, что открывающая скобка извлекается из стека, но
не понимаю, почему это происходит
    

Ответы

Ответ 1

первая ошибка:

stack *begin = NULL;


поскольку после прочтения буквы в следующем цикле  begin остается нулевым, а компилятор
не сможет осуществить проверку:

else {
  if (priority(begin->info) <= priority(input[i])) 
//...


поэтому:

stack *begin = new stack;



и не связанные с вашим вопросом ошибки:`


вторая ошибка:

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

третья ошибка:

вы не возвращаете из функции int priority(char op) ничего, если op не является ни
один из вами перечисленных символов (лучше возвращать ноль и это использовать в ваших
условиях, т.е. если priority(char op)== 0, значит`  op не является символом математической
операции

и напоследок:  еслибы вы хранили один string("*/()%+-"}, то использовав string::find
могли бы сделать этот же код компактней и с меньшим количеством if/else ов


Ответ 2

Забыли проконтролировать скобки в executeFromStackElements.

void executeFromStackElements(string & output, stack *& begin)    {
    while (begin != NULL and begin->info != '(') {
        output += begin->info;
        begin = begin->next;    }}