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

@Pavlin234 · Регистрация: 12.03.2017

Студворк — интернет-сервис помощи студентам

В обратной польской записи, которую также называют постфиксной, операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как «A B +». Запись «B C + D *» обозначает привычное нам (B+C)∗D(B+C)∗D, а запись «A B C + D * +» означает A+(B+C)∗DA+(B+C)∗D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.

Дано выражение в постфиксой записи, содержащее однозначные числа, операции «+», «–», «*». Вычислите значение записанного выражения.

Формат входных данных
В единственной строке записано выражение в постфиксной записи, содержащее однозначные числа и операции «+», «–», «*». Строка содержит не более 100 чисел и операций. Числа и операции отделяются друг от друга ровно одним пробелом.

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

Примечания
В данной задаче рекомендуется считывать данные с экрана в тип char, то есть по одному символу до тех пор, пока не будет встречен перевод строки (символ ’\n’). Для чтения можно использовать функцию getchar() в C++, которая находится в библиотеке #include<cstdio>.

Примеры
входные данные
8 9 + 1 7 - *
выходные данные
-102

@COKPOWEHEU · 01.12.2017, 20:30

Не по теме:

Kuzia domovenok, ваш код шикарен! Понятия не имею что он делает, но он шикарен.
С высказыванием об ожидании и реальности тоже не могу не согласиться.

Nishen · 01.12.2017, 20:39

Не по теме:

Kuzia domovenok, что Вы, ТС ведь свою ОС пишет уже, куда ему до ОПН. :)

@Pavlin234 · 02.12.2017, 17:37 **[ТС]**

Последнее! Программа выводит 102, а не -102. Он не понимает знак - после действий!

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
#include <iostream>
#include <stack>
#include <sstream>
#include<string>
using namespace std;
int main() {
    string str;
    getline(std::cin, str);
    istringstream s(str);
    stack<int> opz;
    int value;
    char sign;
    while (!s.eof())
    {
        while (s >> value) {
            opz.push(value);
        }
        if (!s.eof())
        {
            s.clear();
            s.unget();
            s >> sign;
            if (opz.size() < 2)
            {
                cout << "corrupt oper. order" << endl;
                return 0;
            }
            int right = opz.top();
            opz.pop();
            int left = opz.top();
            opz.pop();
            switch (sign) {
            case '+':   opz.push(right + left); break;
            case '-':   opz.push(right - left); break;
            case '*':   opz.push(right * left); break;
            case '/':   opz.push(right / left); break;
            default:
                cout << "undefined operatop " << sign << endl;
                return 0;
            }
        }
    }
    if (opz.size() != 1)
    {
        cout << "stack corrupted" << endl;
        return 0;
    }
    cout << opz.top() << endl;
    getchar();
    getchar();
    return 0;
}

@ARTER616 · 02.12.2017, 19:12

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

case '-': * opz.push(right - left); break;

заменить на

C++
1
case '-': * opz.push(left-right); break;

Правда, все-равно множество тестов не проходит

@Sebek_001 · 01.03.2020, 14:22

Kuzia domovenok, Можете пожалуйста объяснить пошагово как работает этот отрывок кода?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (! s.eof ())
         {
             s.clear ();
             s.unget ();
             s >> sign;
             if (opz.size () <2)
             {
                 cout << "corrupt oper. order" << endl;
                 return 0;
             }
             int right = opz.top ();
             opz.pop ();
             int left = opz.top ();
             opz.pop ()

Дело в том, что я пробовал переделать этот код под свою задачу и при введении инфиксное выражения из консоли вылетает "corrupt oper. Order". Помогите пожалуйста разобраться.

@Kuzia domovenok · 01.03.2020, 15:05

Sebek_001, пипец, ты умудрился найти мой пост трёхлетней давности, вместо того чтоб открыть википеди!

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

ожете пожалуйста объяснить пошагово как работает этот отрывок кода?

читает сначала число, потом второе число, потом знак
как ты его переделал? тут всё строго на порядок завязано!!!

@Sebek_001 · 01.03.2020, 17:18

Kuzia domovenok, Спасибо, я уже сам разобрался считает все ок. Но вылезла новая проблема не могу превратить обычную нотацию на польский.
вот то что есть но оно не работает

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
stack <char> operation;
    string result;
 
    std::cout << "WELCOME TO THE STACK RPN CALCULATOR" << endl;
 
    //////////////////////////////////////////////////////////////////////////
    operation.push('#');
 
    string expression;
 
    std::cout << ">> ";
    cin >> expression;
    //expression = "(7 - 2 * 3) ^ 4 + 9 / 3";
    int SizeOfExpression = size(expression);
    int priority;
 
    for (int i = 0; i < SizeOfExpression; i++)
    {
        
        priority = Priority(expression[i]);
 
            switch (priority)
            {
            case -5: break;
            case 0:
                if (expression[i] == '.') 
                { 
                    result += '.'; break; 
                }
                else if (expression[i + 1] != ' ') 
                {
                    result += (expression[i]);
                }
                else 
                {
                    result += (expression[i]);
                    result += ' ';
 
                }
                break;
            case 1:
                operation.push(expression[i]);
                break;
            case 2:
                while (Priority(operation.top()) >= priority) 
                {
                    result += operation.top();
                    operation.pop();
                    result += ' ';
                }
                operation.push(expression[i]);
                break;
            case 3:
                while (Priority(operation.top()) >= priority) 
                {
                    result += operation.top();
                    operation.pop();
                    result += ' ';
                }
                operation.push(expression[i]);
                break;
            case 4:
                while (Priority(operation.top()) >= priority) 
                {
                    result += operation.top();
                    operation.pop();
                    result += ' ';
                }
                operation.push(expression[i]);
                break;
            case -1:
                result += ' ';
                while (operation.top() != '(') 
                {
                    result += (operation.top());
                    operation.pop();
                }
                if (operation.top() == '(') { operation.pop(); result += ' '; }
                break;
            }
        
    }
 
    while (operation.top() != '#') 
    {
        result += operation.top();
        operation.pop();
        result += ' ';
    }
 
    
 
    string rpn = result;
 
    std::cout << "RESULT :" << result << endl;
 
    /////////////////////////////////////////////////////////////////////////////
    
    std::cout << "RPN: " << rpn << endl;
    std::cout << "ANSWER: " << Calculation(rpn) << endl;
    system("pause");
    return 0;
}

Calculation(rpn) - ето твоя функция.

@user1673265 · 25.07.2020, 15:08

Поскольку задача является олимпиадной, делать через объекты неэффективно, пушо будет съедать много памяти. Рекомендую
сделать таким образом:

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
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main() {
    stack<int> number;
    string var = "";
    getline(cin, var);
    for (int i = 0; i < var.size(); i++) {
        if (isdigit(var[i])) {
            number.push(var[i] - 48);
        }
        else {
            int val1 = 0;
            int val2 = 0;
            if (var[i] == '+') {
                val1 = number.top();
                number.pop();
                val2 = number.top();
                number.pop();
                number.push(val1 + val2);
            }
            else if (var[i] == '-'){
                val1 = number.top();
                number.pop();
                val2 = number.top();
                number.pop();
                number.push(val2 - val1);
            }
            else if (var[i] == '*'){
                val1 = number.top();
                number.pop();
                val2 = number.top();
                number.pop();
                number.push(val1 * val2);
            }
            else if (var[i] == '/'){
                val1 = number.top();
                number.pop();
                val2 = number.top();
                number.pop();
                number.push(val1 / val2);
            }
        }
    }
    cout << number.top() << endl;
}

@ShadowAT · 10.08.2021, 17:02

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

Что я тогда делаю не так?

Что ты делаешь не так?)
А почему у тебя 2 переменные s ты не думал?)

@alexu_007 · 10.08.2021, 21:54

Да... Интересная задача была. Но к сожалению я её для себя уже решил.

Добавлено через 22 минуты

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

Kuzia domovenok, ваш код шикарен! Понятия не имею что он делает, но он шикарен.

C
1
u=0;r=k;o=f;q=0;o+=1;f=0;o=0;q+=1;y=0;s+=z;j+=i;y+=1;...

Вот этот что-ли? Но это бессмыслица какая-то!

@Kuzia domovenok · 11.08.2021, 11:07

alexu_007, это писалось больше месяца назад! Естесственно я уже не помню, какой смысл я в него закладывал. Скорее всего хотел простейший кодогенератор написать, но всё на что хватило меня -принцип
"переменная" "оператор" "литерал или переменная" "запятая"

@alexu_007 · 11.08.2021, 16:34

C
1
2
3
4
5
6
7
8
9
10
11
12
u=0;
r=k;
o=f;       // o = f
q=0;
o+=1;    // o = o + 1;
f=0;
o=0;       // o = 0, тогда нафига предыдущие операции?
q+=1;    // перед этим q присваивался ноль, не проще сразу присвоить 1?
y=0;
s+=z;
j+=i;
y+=1;    // с y то же, что с q

дальше не смотрел.

@Kuzia domovenok · 11.08.2021, 17:27

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

тогда нафига предыдущие операции?

alexu_007, ты серьёзно задаёшь этот вопрос генератору рандомных операторов?

@alexu_007 · 12.08.2021, 07:22

Сообщение от Kuzia domovenok

ты серьёзно задаёшь этот вопрос генератору рандомных операторов?

Ух ты! А какой в этом сакральный смысл? Может случайно получиться рабочая программа?

@DrOffset · 12.08.2021, 10:25

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

А какой в этом сакральный смысл?

Обфускация

Добавлено через 2 минуты
В английской статье есть более интересные примеры.

@Cosmo chief · 02.08.2022, 13:09

Лично мне мой код нравится больше)

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
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int main() {
    string a = "";
    getline(cin, a);
    vector<int> nums = {};
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == ' ') {
            continue;
        }
        else if ((a[i] >= '0') && (a[i] <= '9')) {
            nums.push_back(int(a[i] - '0'));
        }
        else if ((a[i] == '*') || (a[i] == '+') || (a[i] == '-')) {
            int y = nums[nums.size() - 1]; nums.pop_back();
            int x = nums[nums.size() - 1]; nums.pop_back();
            if (a[i] == '*') {
                nums.push_back(x * y);
            }
            else if (a[i] == '+') {
                nums.push_back(x + y);
            }
            else if (a[i] == '-') {
                nums.push_back(x - y);
            }
        }
    }
    cout << nums[0];
}

и , да мой код принимает только цифры, тоесть запись
"89 + "
даст ответ 17 т.к. 8 и 9 будут приняты как два разных числа

и еще это работает, проверено сириусом

@alexu_007 · 02.08.2022, 17:45

Сообщение от Cosmo chief

и , да мой код принимает только цифры, тоесть запись

Ну плохо. 8 9 это восемь и девять, а 89 это восемьдесят девять.

@SmallEvil · 02.08.2022, 18:47

Сообщение от Cosmo chief

и , да мой код принимает только цифры, тоесть запись

В таком случае полезность вашей программы равна нулю.

@Cosmo chief · 02.08.2022, 22:57

ну я нашел подобную задачу и в ней именно цифры, а для чисел придется дописывать парсер так что не велика проблемма, в общем то я могу это поправить, но сегодня я этим заниматься не буду, ну а олимпиадную часть задачи я решил так что мне в общем то и не надо было писать для чисел

Добавлено через 40 минут
вот код который может работать с числами а не только с цифрами, возможно он не самый оптимальный, потому что работает в два прохода, сначала парсит а потом считает, и еще в нем можно не разделять числа от знаков операций и знаки от знаков, но для самой задачи это бесполезно

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
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int main() {
    string a = "";
    string sample = "";
    getline(cin, a);
    vector<string> samples = {};
    vector<int> nums = {};
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != ' ') {
            if ((a[i] >= '0') && (a[i] <= '9')) {
                sample += a[i];
            }
            else {
                if (sample.size() != 0) {
                    samples.push_back(sample);
                    sample = "";
                }
                samples.push_back(string{ a[i] });
            }
            
        }
        else {
            if (sample.size() != 0) {
                samples.push_back(sample);
                sample = "";
            }
        }
    }
    if (sample.size() != 0) {
        samples.push_back(sample);
        sample = "";
    }
    /*for (int i = 0; i < samples.size(); i++) {
        cout << samples[i] << endl;
    }*/
    for (int i = 0; i < samples.size(); i++) {
        if ((samples[i][0] >= '0') && (samples[i][0] <= '9')) {
            nums.push_back(stoi(samples[i]));
        }
        else if ((samples[i][0] == '*') || (samples[i][0] == '+') || (samples[i][0] == '-')) {
            int y = nums[nums.size() - 1]; nums.pop_back();
            int x = nums[nums.size() - 1]; nums.pop_back();
            if (samples[i][0] == '*') {
                nums.push_back(x * y);
            }
            else if (samples[i][0] == '+') {
                nums.push_back(x + y);
            }
            else if (samples[i][0] == '-') {
                nums.push_back(x - y);
            }
        }
    }
    cout << nums[0];
}

@Cosmo chief · 02.08.2022, 23:05

вот пруфы

Новые блоги и статьи Все статьи Все блоги /
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .

@Pavlin234 11 / 60 / 21 Регистрация: 12.03.2017 Сообщений: 514

	Обратная польская запись 20.11.2017, 14:27. Показов 55942. Ответов 39 Метки нет (Все метки) В обратной польской записи, которую также называют постфиксной, операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как «A B +». Запись «B C + D » обозначает привычное нам (B+C)∗D(B+C)∗D, а запись «A B C + D +» означает A+(B+C)∗DA+(B+C)∗D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения. Дано выражение в постфиксой записи, содержащее однозначные числа, операции «+», «–», «». Вычислите значение записанного выражения. Формат входных данных В единственной строке записано выражение в постфиксной записи, содержащее однозначные числа и операции «+», «–», «». Строка содержит не более 100 чисел и операций. Числа и операции отделяются друг от друга ровно одним пробелом. Формат выходных данных Необходимо вывести значение записанного выражения. Гарантируется, что результат выражения, а также результаты всех промежуточных вычислений по модулю меньше 2³¹. Примечания В данной задаче рекомендуется считывать данные с экрана в тип char, то есть по одному символу до тех пор, пока не будет встречен перевод строки (символ ’\n’). Для чтения можно использовать функцию getchar() в C++, которая находится в библиотеке #include<cstdio>. Примеры входные данные 8 9 + 1 7 - * выходные данные -102 0

@COKPOWEHEU
	01.12.2017, 20:30
	Не по теме: Kuzia domovenok, ваш код шикарен! Понятия не имею что он делает, но он шикарен. С высказыванием об ожидании и реальности тоже не могу не согласиться. 0

Nishen
	01.12.2017, 20:39
	Не по теме: Kuzia domovenok, что Вы, ТС ведь свою ОС пишет уже, куда ему до ОПН. :) 0

@Kuzia domovenok 4268 / 3328 / 926 Регистрация: 25.03.2012 Сообщений: 12,545 Записей в блоге: 1
	11.08.2021, 11:07
	alexu_007, это писалось больше месяца назад! Естесственно я уже не помню, какой смысл я в него закладывал. Скорее всего хотел простейший кодогенератор написать, но всё на что хватило меня -принцип "переменная" "оператор" "литерал или переменная" "запятая" 0

@Cosmo chief 4 / 4 / 0 Регистрация: 11.08.2020 Сообщений: 14
	02.08.2022, 23:05
	вот пруфы Миниатюры 0