Из инфиксной нотации в постфиксную

@GoodDay · Регистрация: 07.04.2012

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

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

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
//
 
 
#include <iostream>
#include <string>
#include <ctype.h>
#define MAX_SIZE 256
using namespace std;
 
class calc
{
private:
    char* infixStroka;
    char* stack;
    char* PostfixStroka; // Выходная строка постфиксной нотации
    int size; //Размер строки
    int n; // Счетчик стека
public:
    calc(char str[])
    {
        n = 0;
        size = strlen(str);
        infixStroka = new char[size];
        stack = new char[size];
        PostfixStroka = new char[size];
        for(int i = 0; i <= size; i++)
        {
            infixStroka[i] = str[i];
            stack[i] = NULL;
        }
    }
    void push(char b)
    {
        stack[n] = b;
        n++;
    }
    char pop()
    {
        return stack[n--];
    }
    void InftoPost()
    {
 
        int j = 0;
        for(int i = 0; i < size; i++)
        {
            cout << infixStroka[i] << "stroka" << endl;
            cout << stack[n] << "stack" << endl;
            if(infixStroka[i] == '+' || infixStroka[i] == '-' || infixStroka[i] == '*' || infixStroka[i] == '/' || infixStroka[i] == '^')
                this->push(infixStroka[i]);
            else if(isdigit(infixStroka[i]) || infixStroka[i] == 'x')
            {
                PostfixStroka[j] = infixStroka[i];
                j++;
            }
            else if(infixStroka[i] == '(')
                this->push(infixStroka[i]);
            else if(infixStroka[i] == ')')
            {
                char good = this->pop();
                do
                {
                    PostfixStroka[j] = good;
                    good = this->pop();
                    j++;
                }
                while(good != '(');
            }   
 
 
        }
        while(n != 0)
            PostfixStroka[j++] = this->pop();
 
    }
    void display()
    {
        cout << "infixStroka: " << infixStroka << endl;
        cout << "PostFixStroka: " << PostfixStroka << endl;
    }
};
int main()
{
    calc a("3+4+5*6+7");
    a.InftoPost();
    a.display();
    return 0;
}

P.S Дальше программа должна данную строку вычислять( X это переменная), но это уже когда разберусь с переводом). И можно пожалуйста найти ошибку в моем алгоритме, а не переписывать буду очень благодарен.

Спасибо

Добавлено через 2 часа 35 минут
Неужели никто не знает? Тут ошибка в том что в стек не идет запись, а как исправить....

@monolit · 13.12.2013, 20:33

Во первых, это что такое:

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

stack[i] = NULL;

Я понимаю, что макрос, и все такое, но если решил писать вместо нуля всякие штуки, то нужно знать, где нужно, а где нет. stack[i] - не указатель =>

C++
1
stack[i] = 0;

можно было б stack=NULL, но это другой вопрос.
Во вторых, codepad.org ругается на конструктор, да оно и верно: в таких случаях лучше писать так, не ошибешься и потенциальных ошибок не будет:

C++
1
calc(const char* str)

По теме:
первое. У тебя неправильный pop. Надо так:

C++
1
2
3
4
char pop()
    {
        return stack[--n]; // n ведь указывало на следующий за последним, т.е. посл. - (n-1)-й
    }

второе. Память выделяй на 1 больше чем размер входной - не забывай про '\0', и не забывай в конце calc

C++
1
PostfixStroka[j]='\0';

третье. Алгоритм у тебя неправильный. Он то переводит в постфиксную, но приоритеты (а в оригинальном алгоритме учитываются приоритеты операций) не учитывает -> правильно будет работать только с +/-. А приоритеты учитывать надо...
ну и напоследок. Зачем писать везде this->pop() и т.п., т.е. использовать this? Другую функцию, не this, он и не вызовет, нету ее просто, поэтому это лишнее.
Вот такие дела.

@GoodDay · 24.12.2013, 03:50 **[ТС]**

Вроде переправил, перевод работает, но функция которая должна вычислять выражение не работает, где ошибка? Спасибо.

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <iostream>
#include <cstring>
 
using namespace std;
 
 
#define MAX_LEN 256
char stack[MAX_LEN];    // стек для хранения операторов при преобразовании
int st_ptr = 0;             // указатель вершины стека
 
void push(char *_stack, int &_ptr, char data);
char pop(char *_stack, int &_ptr);
 
//
//  Преобразование записи математ. выражения из инфиксной в постфиксную (в обратную польскую запись)
//
//  Сразу оговоримся, допустимые операторы: +,-,*,/,(,),^; все операции будем считать лево-ассоциативными
//  Все операнды - односимвольные
//
void PostfixNotation(const char *_infix, char *_postfix)
{
 
 
    int out_index = 0;      // индекс в выходной строке
    int in_index = 0;       // индекс во входной строке
 
    // начинаем разбор входящей строки (она не должна быть пустой)
    do
    {
        char c = _infix[in_index];  // берем текущий символ входной строки
 
        switch (c)
        {
            case '+':
            case '-':
                // выталкиваем из стека в выходную строку все операторы с большим или равным приоритетом
                while (st_ptr != 0)
                {
                    char op = stack[st_ptr-1];  // оператор в вершине стека
                    if (op != '(')  // все операторы, кроме откр. скобки имеют больший или равный приоритет
                    {
                        _postfix[out_index++] = op; // добавляем оператор в выходную строку
                        pop(stack, st_ptr);         // удаляем оператор из стека
                    }
                    else
                        break;
                }
                // помещаем оператор в стек
                push(stack, st_ptr, c);
                break;
 
            case '*':
            case '/':
                // выталкиваем из стека в выходную строку все операторы с большим или равным приоритетом
                while (st_ptr != 0)
                {
                    char op = stack[st_ptr-1];
                    if ((op == '^') || (op == '*') || (op == '/'))
                    {
                        _postfix[out_index++] = op; // добавляем оператор в выходную строку
                        pop(stack, st_ptr);         // удаляем оператор из стека
                    }
                    else
                        break;
                }
                // помещаем оператор в стек
                push(stack, st_ptr, c);
                break;
 
            case '(':
                // просто помещаем в стек
                push(stack, st_ptr, c);
                break;
 
            case ')':
                // выталкиваем из стека в выходную строку все элементы до открывающей скобки (откр. скобку просто отбрасываем)
                while (st_ptr != 0)
                {
                    char op = pop(stack, st_ptr);   // забираем из стека оператор
                    if (op == '(')                  // если достигли открывающей скобки
                        break;                      // выталкивание закончили
                    else
                    {
                        _postfix[out_index++] = op; // добавили оператор в выходную строку
                    }
                }
                break;
 
            case '^':
                // помещаем оператор в стек (выталкивать ничего не нужно, нет операторов с большим приоритетом)
                push(stack, st_ptr, c);
                break;
 
            default:        // символ цифры
                _postfix[out_index] = c;    // добавляем цифру в выходную строку
                out_index++;
                break;
        }
 
        in_index++; // переходим к следующему символу входной строки
    }
    while (_infix[in_index] != 0);  // разбор закончен
 
    // выталкиваем все операторы в выходную строку
    while(st_ptr != 0)
    {
        _postfix[out_index++] = pop(stack, st_ptr);
        cout << st_ptr << endl;
    }
 
    // завершающий символ нуля
    _postfix[out_index] = 0;
}
 
void calculation(const char* postfix, char* result)
{
    int in_index = 0;
    int out_index = 0;
    st_ptr = 0;
    int first_numb, two_numb;
 
    do
    {
        char c = postfix[in_index];
        char mas[10];
        switch(c)
        {
            char result;
            case '+':
                first_numb = isdigit(pop(stack,st_ptr));
                two_numb = isdigit(pop(stack,st_ptr));
                push(stack,st_ptr,(char)(two_numb + first_numb));
                break;
            case '-':
                first_numb = isdigit(pop(stack,st_ptr));
                two_numb = isdigit(pop(stack,st_ptr));
                push(stack,st_ptr,(char)(two_numb - first_numb));
                break;
            case '*':
                first_numb = isdigit(pop(stack,st_ptr));
                two_numb = isdigit(pop(stack,st_ptr));
                push(stack,st_ptr,(char)(two_numb * first_numb));
                break;
            case '/':
                first_numb = isdigit(pop(stack,st_ptr));
                two_numb = isdigit(pop(stack,st_ptr));
                push(stack,st_ptr,(char)(two_numb / first_numb));
                break;
            case '^':
                first_numb = isdigit(pop(stack,st_ptr));
                two_numb = isdigit(pop(stack,st_ptr));
                push(stack,st_ptr,(char)(two_numb ^ first_numb));
                break;
            default:
                push(stack, st_ptr, c);
                break;
 
 
        }
        in_index++;
    }while(postfix[out_index] != 0);
    while(st_ptr != 0)
    {
        result[out_index++] = pop(stack,st_ptr);
    }
}
 
 
 
void push(char *_stack, int &_ptr, char data)
{
    _stack[_ptr++] = data;
}
 
char pop(char *_stack, int &_ptr)
{
    return _stack[--_ptr];
}
 
 
int main()
{
    char str_infix[] = "(2+2)*3+5*(5+3)";
    char str_postfix[MAX_LEN];
    char result[MAX_LEN];
    cout << str_infix << endl;
    PostfixNotation(str_infix, str_postfix);
        cout << str_postfix << endl;
 
    calculation(str_postfix, result);
    cout << result << endl;
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Хак домофона или как открыть дверь по номеру yariko 25.06.2025 Забыли дома ключ. Не проблема. Можно открыть дверь домофона, просто позвонив на свой номер квартиры. Идея состоит в следующем. Внутрь трубки абонента встраивается контроллер, который по звонку сам. . .	Как украсить новогоднюю елку с Q# и Qiskit EggHead 24.06.2025 Что может быть необычнее, чем применить законы квантовой механики для украшения новогодней елки? Пока другие развешивают обычные гирлянды, я решил объединить свою страсть к квантовым вычислениям с. . .	Системы нулевого доверия на C# UnmanagedCoder 24.06.2025 Традиционная архитектура безопасности работает по принципу средневекового замка: создаём высокие стены вокруг корпоративной сети, укрепляем ворота межсетевыми экранами и системами обнаружения. . .	Снова не мой путь. Циклическое среднее, я обеими руками за проверку условия, в ракурсе данной задачи - циклическое среднее в топку. Hrethgir 24.06.2025 Привет. Такой вопрос - нужно выводить среднее математическое между двумя направлениями, интервал значений которых может лежать в диапазоне одного оборота по кругу. Проблема заключается в том, что. . .	Деплой Flask приложения py-thonny 23.06.2025 За годы работы с Flask я натыкался на одни и те же грабли достаточно часто, чтобы наконец научится их обходить. И сегодня хочу поделится опытом, который сбережет вам немало нервных клеток. Начнем с. . .
WebAssembly и контейнеры в .NET Aspire для оркестрации распределенных архитектур ArchitectMsa 23.06.2025 Я наблюдаю, как WebAssembly (или просто WASM) постепенно выходит за рамки своего первоначального предназначения — исполнения кода на стороне браузера. Теперь эта технология проникает в серверную. . .	Непрерывная интеграция для пакета Python Mr. Docker 22.06.2025 Было 4 часа утра пятницы, когда я выпустил новую версию нашей внутренней библиотеки для обработки данных. Релиз 0. 5. 2 содержал небольшой фикс для обработки дат в ISO формате, что может пойти не так?. . .	Продвинутый ETL на C# из OLTP БД в хранилище stackOverflow 22.06.2025 Работая в сфере корпоративной аналитики, я постоянно сталкиваюсь с одним и тем же - нужны чистые, структурированные и, главное, свежие данные. Без них современные аналитические системы, машинное. . .	Мастер-класс по микросервисам на Node.js Reangularity 21.06.2025 Node. js стал одной из самых популярных платформ для микросервисной архитектуры не случайно. Его неблокирующая однопоточная модель и событийно-ориентированный подход делают его идеальным для. . .	Управление Arduino из WPF приложения Wired 21.06.2025 Зачем вообще связывать Arduino с WPF-приложением? Казалось бы, у Arduino есть собственная среда разработки, своя экосистема, свои способы управления. Однако при создании серьезных проектов. . .

Опции темы