Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/48: Рейтинг темы: голосов - 48, средняя оценка - 4.88
2 / 2 / 1
Регистрация: 25.09.2013
Сообщений: 13
1

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

26.10.2014, 15:29. Просмотров 8616. Ответов 9
Метки нет (Все метки)

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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#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;
}
1
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.10.2014, 15:29
Ответы с готовыми решениями:

Обратная польская запись
Простите что не совсем в том разделе, просто его больше всего людей посещает) По теме: Как при...

Обратная польская запись
Пожалуйста помогите, всю голову себе сломал. Задание: &quot;Обеспечить перевод инфиксного выражения в...

Обратная польская запись
Здравствуйте, изучаю обратную польскую запись, столкнулся с такой проблемой: Перерыл множество...

Обратная польская запись
В обратной польской записи, которую также называют постфиксной, операция записывается после двух...

9
43 / 43 / 12
Регистрация: 06.10.2014
Сообщений: 135
26.10.2014, 17:58 2
Лучший ответ Сообщение было отмечено EternalSeeker как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
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.
1
2 / 2 / 1
Регистрация: 25.09.2013
Сообщений: 13
27.10.2014, 08:03  [ТС] 3
Спасибо, даже в голову не пришло, что нужно их все записывать
А вот про
Цитата Сообщение от ViktorB Посмотреть сообщение
prior(3)
я не совсем понял...
0
Эксперт С++
4967 / 3074 / 456
Регистрация: 10.11.2010
Сообщений: 11,159
Записей в блоге: 10
27.10.2014, 08:11 4
А почему у операций сложения и вычитания приоритет выше чем у деления и умножения?
0
2 / 2 / 1
Регистрация: 25.09.2013
Сообщений: 13
27.10.2014, 08:21  [ТС] 5
Как выше? У сложения и вычитания он 2, а у умножения и деления 3. Вроде все верно...
0
Эксперт С++
4967 / 3074 / 456
Регистрация: 10.11.2010
Сообщений: 11,159
Записей в блоге: 10
27.10.2014, 08:58 6
Выше - меньше. У скобок же самый высокий.
0
2 / 2 / 1
Регистрация: 25.09.2013
Сообщений: 13
27.10.2014, 09:22  [ТС] 7
Ах вон оно что, то есть должно быть вот так?
C++
1
2
3
4
5
6
7
8
9
int prior(char v){
    switch(v){
        case '+':
        case '-': return 3;
        case '*':
        case '/': return 2;
        case '(': return 1;
    }
}
0
Эксперт С++
4967 / 3074 / 456
Регистрация: 10.11.2010
Сообщений: 11,159
Записей в блоге: 10
27.10.2014, 09:25 8
Если в твоей программе 1 считается высшим приоритетом, тогда да.
1
43 / 43 / 12
Регистрация: 06.10.2014
Сообщений: 135
27.10.2014, 11:12 9
Цитата Сообщение от EternalSeeker Посмотреть сообщение
Ах вон оно что, то есть должно быть вот так?
Не надо менять приоритет открывающей скобки на высший. Этот алгоритм так рассчитан, что скобки обрабатываются отдельно от операторов. В стек добавляется только открывающая скобка. При поступлении закрывающей скобки она никуда не добавляется, а выполняется извлечение содержимого стека в выходную строку, пока не будет встречена открывающая скобка. Сама открывающая скобка тоже извлекается со стека, но в выходную строку не добавляется.

Если поставить самый высокий приоритет для открывающей скобки, то она будет выталкиваться из стека каждый раз при обработке операторов в блоке else if (is_op...). Конкретно, вот здесь
C++
1
2
3
4
5
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, паттерн. В большом проекте такой стиль может сэкономить время и нервы
1
2 / 2 / 1
Регистрация: 25.09.2013
Сообщений: 13
29.10.2014, 09:55  [ТС] 10
Слушай, а можно еще спросить?
Вот у меня такая загвоздка, если я введу в инфиксной a+a, то есть две одинаковые переменные, и он запросит эту переменную оба раза. А как сделать так, чтобы он запоминал значение этой переменной. Я думал сделать тремя массивами: массив с переменной, массив со значением и массив с флагами (используется переменная или нет), но это как то слишком мудрено...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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());
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.10.2014, 09:55

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

Обратная польская запись
Доброго времени суток. Нужно сделать программу которая переводит арифм. выражение в обратную...

Обратная польская запись
Нужна помощь. Есть программа с общей польской записью. Программа принимает только буквенное...

Обратная польская запись
Что такое обратная польская запись и как её реализовать на С++? Почему когда в программе я пишу...

Обратная польская запись
Написать программу формирования ОПЗ и расчета полученного вы-ражения. Разработать удобный интерфейс...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.