Обратная Польская Запись

@EternalSeeker · Регистрация: 25.09.2013

Сам вопрос:
Я написал программу, она работает, но препод по Структурам данных сломал ее в два счета. Я нашел ошибку, но как ее исправить я не понимаю. Если вводиться выражение, например, a+b*c-d, то верный ответ в постфиксной форме - это abc*+d-, а моя программа выдает abc*d-+. То есть когда у операторов одинаковые приоритеты, они должны выполняться слева направо, а у меня справа налево.

В голову ничего не приходит, надеюсь на вашу помощь

C++

#include <iostream>
#include <cctype>
#include <stdlib.h>
#include <conio.h>
#include <stack>
 
using namespace std;
 
int prior(char v){
    switch(v){
        case '(': return 1;
        case '+': 
        case '-': return 2;
        case '*': 
        case '/': return 3;
    }   
}
bool is_op(char c){
    return c=='+' || c=='-' || c=='*' || c=='/';
}
bool is_alpha(char c){
    return c>='a' && c<='z';
}
void OPN(char *a, char *out){
    stack <char> S;
    int i = 0, j = 0;
    char t;
    while (a[i] != '\0'){
        if (is_alpha(a[i])){
            out[j] = a[i];
            j++;
        } else if (is_op(a[i])){
            if (S.empty() || prior(S.top()) < prior(a[i])){
               S.push(a[i]);
            } else if (prior(S.top()) >= prior(a[i])) {
                out[j] = S.top(); 
                S.pop(); 
                S.push(a[i]);
                j++;
            }
        } else if (a[i] == '('){
           S.push(a[i]);
        } else if (a[i] == ')'){
            if (S.empty() || S.top() == '('){
               cout << "Input error!";
                getch(); exit(1);
            } else {
                while (S.top() != '('){
                    out[j] = S.top(); 
                    S.pop(); 
                    j++;
                }
            }
            S.pop();
        }
        i++;
    }
    while (!S.empty()){
        if (S.top() == '('){
            cout << "Input error!";
            getch(); exit(1);
        } else {
            out[j] = S.top(); 
            S.pop(); 
            j++;
            
        }
    }
}
int Calc(char *out){
    int j = 0, c = 0, r1 = 0, r2 = 0;
    stack <double> S;
    stack <double> S1;
    while (out[j] != '\0'){
        if (out[j]>='a' && out[j]<='z'){
            cout << "\nEnter " << out[j] << ": "; cin >> c;
            S.push(c);
        } else if (is_op(out[j])){
            r1 = S.top(); S.pop();
            r2 = S.top(); S.pop();
            switch(out[j]){
                case '+': S.push(r2+r1); break;
                case '-': S.push(r2-r1); break;
                case '*': S.push(r2*r1); break;
                case '/': S.push(r2/r1); break;
            }
        }
        j++;   
    }
    return (S.top());
}
 
int main(){
    char a[100] = {0};
    char out[100] = {0};
    stack <char> S;
    int i = 0;
    
    cout << "a: "; gets(a); 
    
    OPN(a,out);
    
    cout << "out: " << out;
    
    cout << "answer: " << Calc(out);
                
    cout << "\nEnd.\n";
    getch();
    return 0;
}

@ViktorB · 26.10.2014, 17:58

C++

if (S.empty() || prior(S.top()) < prior(a[i]))
{
    S.push(a[i]);
}
else
{
    while (!S.empty() && (prior(S.top()) >= prior(a[i]))) // Нужно все операции с не меньшим приоритетом переписывать в выходную строку, а не одну
    {
        out[j++] = S.top();
        S.pop();
    }
    S.push(a[i]);
}

Еще так навскидку:
Что будет, если по ошибке вызвать prior(3)?
В Calc надо бы определиться что вам нужно double или int.

@EternalSeeker · 27.10.2014, 08:03 **[ТС]**

Спасибо, даже в голову не пришло, что нужно их все записывать

А вот про

Сообщение от ViktorB

prior(3)

я не совсем понял...

@castaway · 27.10.2014, 08:11

А почему у операций сложения и вычитания приоритет выше чем у деления и умножения?

@EternalSeeker · 27.10.2014, 08:21 **[ТС]**

Как выше? У сложения и вычитания он 2, а у умножения и деления 3. Вроде все верно...

@castaway · 27.10.2014, 08:58

Выше - меньше. У скобок же самый высокий.

@EternalSeeker · 27.10.2014, 09:22 **[ТС]**

Ах вон оно что, то есть должно быть вот так?

C++

int prior(char v){
    switch(v){
        case '+':
        case '-': return 3;
        case '*':
        case '/': return 2;
        case '(': return 1;
    }
}

@castaway · 27.10.2014, 09:25

Если в твоей программе 1 считается высшим приоритетом, тогда да.

@ViktorB · 27.10.2014, 11:12

Сообщение от EternalSeeker

Ах вон оно что, то есть должно быть вот так?

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

Если поставить самый высокий приоритет для открывающей скобки, то она будет выталкиваться из стека каждый раз при обработке операторов в блоке else if (is_op...). Конкретно, вот здесь

C++

while (!S.empty() && (prior(S.top()) >= prior(a[i])))
{
    out[j++] = S.top();
    S.pop();
}

Естественно, что эта открывающая скобка будет попадать в выходную строку, т.е. в польскую нотацию, где скобки вообще не должны появляться. Это не сложно исправить, но... Возможно (это зависит от приоритета следующего оператора на стеке), что за открывающей скобкой будут извлечены еще последующие операторы. При этом, конечно же, никакой закрывающей скобки в парсер еще не поступило. А вот когда парсер встретит закрывающую скобку, он начнет извлекать со стека все подряд, пока не встретит открывающую скобку, но... Открывающую скобку парсер там уже не найдет. Короче все сломается.
В общем в этом алгоритме нужно назначать открывающей скобке самый низкий приоритет.

Сообщение от EternalSeeker

А вот про
Сообщение от ViktorB
prior(3)
я не совсем понял...

Я это к тому, что у вас не все варианты возврата из функции в switch обрабатываются. Например, что вернет вызов prior(3) или prior(':')? Т.е. следует добавить default и что-то там сделать, если не подходящий параметр поступил. Например, если эта функция используется только в этой программе, то достаточно выдать сообщение в отладчное окно и вернуть что-нибудь. В вашем случае вполне сойдет:

C++

1
2
3

default:
    printf("Invalid parameter \'%d\' in %s\n", v, __FUNCTION__);
    return 0;

Можно, конечно, не заморачиваться пока на этом, у вас все будет работать и так. Но это, так сказать, это best practice, паттерн. В большом проекте такой стиль может сэкономить время и нервы

@EternalSeeker · 29.10.2014, 09:55 **[ТС]**

Слушай, а можно еще спросить?
Вот у меня такая загвоздка, если я введу в инфиксной a+a, то есть две одинаковые переменные, и он запросит эту переменную оба раза. А как сделать так, чтобы он запоминал значение этой переменной. Я думал сделать тремя массивами: массив с переменной, массив со значением и массив с флагами (используется переменная или нет), но это как то слишком мудрено...

C++

int Calc(char *out){
    int j = 0, c = 0, r1 = 0, r2 = 0;
    stack <double> S;
    stack <double> S1;
    while (out[j] != '\0'){
        if (out[j]>='a' && out[j]<='z'){
            cout << "\nEnter " << out[j] << ": "; cin >> c;
            S.push(c);
        } else if (is_op(out[j])){
            r1 = S.top(); S.pop();
            r2 = S.top(); S.pop();
            switch(out[j]){
                case '+': S.push(r2+r1); break;
                case '-': S.push(r2-r1); break;
                case '*': S.push(r2*r1); break;
                case '/': S.push(r2/r1); break;
            }
        }
        j++;   
    }
    return (S.top());
}

@EternalSeeker 2 / 2 / 1 Регистрация: 25.09.2013 Сообщений: 13
	27.10.2014, 08:03 [ТС]	3
	Спасибо, даже в голову не пришло, что нужно их все записывать А вот про Сообщение от ViktorB prior(3) я не совсем понял... 0

@castaway 4967 / 3074 / 456 Регистрация: 10.11.2010 Сообщений: 11,159 Записей в блоге: 10
	27.10.2014, 08:11	4
	А почему у операций сложения и вычитания приоритет выше чем у деления и умножения? 0

@EternalSeeker 2 / 2 / 1 Регистрация: 25.09.2013 Сообщений: 13
	27.10.2014, 08:21 [ТС]	5
	Как выше? У сложения и вычитания он 2, а у умножения и деления 3. Вроде все верно... 0

@castaway 4967 / 3074 / 456 Регистрация: 10.11.2010 Сообщений: 11,159 Записей в блоге: 10
	27.10.2014, 08:58	6
	Выше - меньше. У скобок же самый высокий. 0

@castaway 4967 / 3074 / 456 Регистрация: 10.11.2010 Сообщений: 11,159 Записей в блоге: 10
	27.10.2014, 09:25	8
	Если в твоей программе 1 считается высшим приоритетом, тогда да. 1

Опции темы

Обратная Польская Запись

Решение