Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
GoodDay
0 / 0 / 0
Регистрация: 07.04.2012
Сообщений: 24
13.12.2013, 19:49     Из инфиксной нотации в постфиксную #1
Здравствуйте, прошу помощи, есть класс в нем методы. Суть программы в том что она должна переводить из инфиксной нотации в постфисную, но где то накосячил, понять не могу где

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 минут
Неужели никто не знает? Тут ошибка в том что в стек не идет запись, а как исправить....
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2013, 19:49     Из инфиксной нотации в постфиксную
Посмотрите здесь:

Выражение в инфиксной форме. СРОЧНО!!! C++
Нотации массивов и указателей C++
C++ Преобразовать выражение в постфиксную форму
Перевести выражение из инфиксной формы в постфиксную C++
Из инфиксной в постфиксную C++
C++ Перевод из инфиксной в постфиксную запись
Преобразовать выражение в префиксной форме в постфиксную (C -> C++) C++
C++ Написать программу преобразования инфиксной формы выражения в постфиксную (память)
Узнать какая фигура удалена по шахматной нотации C++
C++ Определить цвет шахматного поля, заданного в стандардной нотации
C++ Посчитать значение выражения, записанного в обратной польской нотации
Неверный перевод в постфиксную форму C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
monolit
180 / 180 / 21
Регистрация: 24.03.2011
Сообщений: 647
Завершенные тесты: 1
13.12.2013, 20:33     Из инфиксной нотации в постфиксную #2
Во первых, это что такое:
Цитата Сообщение от 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
0 / 0 / 0
Регистрация: 07.04.2012
Сообщений: 24
24.12.2013, 03:50  [ТС]     Из инфиксной нотации в постфиксную #3
Вроде переправил, перевод работает, но функция которая должна вычислять выражение не работает, где ошибка? Спасибо.

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;
}
Yandex
Объявления
24.12.2013, 03:50     Из инфиксной нотации в постфиксную
Ответ Создать тему
Опции темы

Текущее время: 11:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru