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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Мизантроп_Лол
13 / 13 / 2
Регистрация: 26.02.2013
Сообщений: 285
Завершенные тесты: 1
#1

Парсер для математических выражений - C++

05.07.2015, 18:27. Просмотров 1168. Ответов 19
Метки нет (Все метки)

Здравствуйте уважаемые товарищи форумчане. Я пишу интерпретатор математических выражений и, собственно, для этого, сначала перевожу выражение в обратную польскую нотацию. Уже было вроде как закончил и хотел проверить работоспособность перевода, однако CodeBlocks посчитал иначе. Приложение запускается, однако в консоль вылетает ошибка и все. Приложение виснет. Я хотел пройтись пошагово, однако это нечто вылетает сразу же при старте. Ошибку можно увидеть на скриншоте. Исходники:
parser.h
C++
1
2
3
4
5
6
7
8
9
#ifndef PARSER_H_INCLUDED
#define PARSER_H_INCLUDED
 
namespace Parser
{
    std::string toPolish(std::string s);
}
 
#endif // PARSER_H_INCLUDED
parser.cpp
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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
#include <string>
#include <map>
#include <stdio.h>
#include "errors.h"
#include "parser.h"
 
namespace __Stack
{
    struct Stack
    {
        std::string value;
        Stack *next;
    };
 
    Stack *tail = NULL;
 
    void        push(std::string);
    std::string pop();
    void        clear();
}
 
void __Stack::push(std::string value)
{
    Stack *stk = new Stack();
 
    stk->value = value;
    stk->next = tail;
 
    tail = stk;
}
 
std::string __Stack::pop()
{
    std::string result = tail->value;
    Stack *stk = tail;
 
    tail = tail->next;
    delete stk;
 
    return result;
}
 
void __Stack::clear()
{
    Stack *stk;
 
    while (tail)
    {
        stk = tail;
        tail = tail->next;
        delete stk;
    }
}
 
///////////////////////////////////////////////////////////////////
 
namespace __Parser
{
    enum eTokens
    {
        NAME,           NUMBER,          FUNC,      U_MINUS,
        PLUS = '+',     MINUS = '-',     MUL = '*', DIV = '/',
        POW  = '^',     SQRT  = '\\',
        L_BRUNCH = '(', R_BRUNCH = ')'
    };
 
    eTokens curr_token;
    uint16_t char_pos = 0;
    //Используется для определения, является знак '+' или '-'
    //унарным или бинарным.
    //Если это начало выражения или перед текущим знаком была бинарная
    //операция или открывающая скобка - знак унарный.
    bool sign = true;
    //Имя переменной
    std::string x_name;
    std::string functions = {"sin", "cos"};
    std::map<eTokens, int> token_priority = {{L_BRUNCH, 0},
                                             {R_BRUNCH, 0},
                                             {PLUS,     1},
                                             {MINUS,    1},
                                             {MUL,      2},
                                             {DIV,      2},
                                             {POW,      3},
                                             {SQRT,     3},
                                             {U_MINUS,  4},
                                             {FUNC,     5}};
    const int funcs_count = 2;
 
    inline char getChar(std::string &);
    inline void backChar();
    bool        isFunc(std::string &);
    std::string getNumber(std::string &);
    std::string getName(std::string &);
    std::string getToken(std::string &);
    std::string pop();
    void        deleteSpaces(std::string);
    std::string toPolish(std::string &);
}
 
char __Parser::getChar(std::string &s)
{
    return s[char_pos++];
}
 
void __Parser::backChar()
{
    char_pos--;
}
 
bool __Parser::isFunc(std::string &s)
{
    for (int i = 0; i<funcs_count; i++)
    {
        if (s.find(functions[i]))
        {
            return true;
        }
    }
    return false;
}
 
std::string __Parser::getNumber(std::string &s)
{
    std::string result;
    char c = getChar(s);
 
    while ((c>'0') && (c<'9'))
    {
        result += c;
        if (char_pos == s.length() - 1)
        {
            return result;
        }
        c = getChar(s);
    }
    backChar();
 
    return result;
}
 
std::string __Parser::getName(std::string &s)
{
    std::string result;
    char c = getChar(s);
    bool end_str = false;
 
    while (isalpha(c))
    {
        result += c;
        if (char_pos == s.length() - 1)
        {
            end_str = true;
            break;
        }
        c = getChar(s);
    }
    if (!end_str)
    {
        backChar();
    }
 
    if (isFunc(result))
    {
        curr_token = FUNC;
    }
    else
    {
        curr_token = NAME;
        if (x_name.empty())
        {
            x_name = result;
        }
        else
        {
            throw Error("ошибка: неверное имя переменной", char_pos - result.length());
        }
    }
 
    return result;
}
 
std::string __Parser::getToken(std::string &s)
{
    char c = getChar(s);
 
    switch (c)
    {
        case '+': case '-':  case '*': case '/':
        case '^': case '\\': case '(': case ')':
            curr_token = (eTokens)c;
            std::string result;
            result += c;
            return result;
    }
 
    if ((c>'0') && (c<'9'))
    {
        backChar();
        curr_token = NUMBER;
        return getNumber(s);
    }
 
    return getName(s);
}
 
std::string __Parser::pop()
{
    std::string result = __Stack::pop();
    return getToken(result);
}
 
void __Parser::deleteSpaces(std::string s)
{
    for (uint16_t i = 0; i<s.length(); i++)
    {
        if (s[i] == ' ')
        {
            s.erase(i, 1);
        }
    }
}
 
std::string __Parser::toPolish(std::string &s)
{
    char_pos = 0;
    sign = true;
 
    int last = s.length() - 1;
    std::string result;
    std::string token_value;
    __Stack::clear();
 
    using __Stack::push;
    while (char_pos != last)
    {
        token_value = getToken(s);
        switch (curr_token)
        {
            case NUMBER:
            {
                sign = false;
                result += token_value + " ";
                break;
            }
 
            case L_BRUNCH:
            {
                sign = true;
                push(token_value);
                break;
            }
 
            case R_BRUNCH:
            {
                sign = false;
                while (true)
                {
                    token_value = pop();
                    if (curr_token == L_BRUNCH)
                    {
                        break;
                    }
                    result += token_value + " ";
                }
                break;
            }
 
            case PLUS:{} case MINUS:{} case MUL:{}
            case DIV:{}  case POW:{}   case SQRT:{}
            case FUNC:
            {
                if (curr_token == MINUS)
                {
                    if (sign)
                    {
                        curr_token = U_MINUS;
                    }
                }
                sign = false;
                eTokens tok = curr_token;
                std::string buff;
                while (true)
                {
                    buff = pop();
                    if (token_priority[curr_token]>=token_priority[tok])
                    {
                        result += buff + " ";
                    }
                    else
                    {
                        break;
                    }
                }
                push(buff);
                push(token_value);
                break;
            }
 
            case NAME:
            {
                sign = false;
                result += token_value + " ";
                break;
            }
 
            default:
            {
                throw Error("ошибка: неизвестный токен", char_pos);
                break;
            }
        }
    }
 
    return result;
}
 
std::string Parser::toPolish(std::string s)
{
    __Parser::deleteSpaces(s);
    return __Parser::toPolish(s);
}
main.cpp
C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
#include "parser.h"
 
using namespace std;
 
int main()
{
    cout << Parser::toPolish("x + 2");
}
P.S.
Еще хотел бы попросить, если не сложно, оценить код, может что-то посоветовать, за что-то наругать, за что-то кинуть тапком и т.д. А то мало ли.
P.P.S.
Обработка ошибок пока что только в зародыше, поэтому на нее не смотрите.

Благодарю за внимание.
0
Миниатюры
Парсер для математических выражений  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.07.2015, 18:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Парсер для математических выражений (C++):

Написать парсер математических выражений с функцией упрощения этих выражений - C++
Люди, здравствуйте. Есть такая задача: написать упроститель выражений. На вход подается строка вида &quot;a*b+a*c&quot;, являющаяся корректным...

Парсер математических выражений - C++
знаю изъезженная тема, надо написать парсер мат выражений с поддержкой скобок и некоторых несложных функций типа: sin, cos, tg, ctg, ln......

Парсер математических выражений на С/С++ - C++
Добрый вечер, можете написать или помочь написать парсер математических выражений для программы вычисляющей интеграл

Парсер математических выражений - можно ли оптимизировать и улучшить код - C++
Добрый день возник следующий вопрос, в программировании не сильно большой гуру пошел на собеседование , дали тестовое задание парсер...

Парсер математических выражений на с++ визуал студио 2013 в windows forms перевести в обратную пз - C++
нужно сделать парсер перевести в обратную польскую запись затем посчитать в окне

Вычисление математических выражений - C++
Всем привет, я пишу этот пост в связи с тем что, мне дали это задание не обьяснив как её правильно написать. Я учусь на данный момент на...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Мизантроп_Лол
13 / 13 / 2
Регистрация: 26.02.2013
Сообщений: 285
Завершенные тесты: 1
05.07.2015, 19:32  [ТС] #2
Up.
0
Fulcrum_013
721 / 746 / 73
Регистрация: 14.12.2014
Сообщений: 5,913
Завершенные тесты: 3
05.07.2015, 19:46 #3
Цитата Сообщение от Мизантроп_Лол Посмотреть сообщение
собственно, для этого, сначала перевожу выражение в обратную польскую нотацию
Брось заниматься глупостями. Распознавай выражение справа на лево, так как делают все нормальные люди со времен Кернигана и Ритча, и тогда никакая сортировочная станция не нужна, приоритет сохраняется автоматически.
0
Renji
1921 / 1319 / 298
Регистрация: 05.06.2014
Сообщений: 3,779
05.07.2015, 19:52 #4
Цитата Сообщение от Мизантроп_Лол Посмотреть сообщение
Еще хотел бы попросить, если не сложно, оценить код, может что-то посоветовать, за что-то наругать, за что-то кинуть тапком и т.д. А то мало ли.
1) Осваивать чтение из потока stringstream. У вас явно тот же потоковый ввод, только через велосипед.
2) Нафиг enum, нафиг switch по ним. Каждая элементарная операция описывается объектом function, в этом объекте лежит виртуальная функция calculate, которая эту элементарную операцию и считает.
3) Через древо разбора функцию считать не удобнее будет? По крайней мере, не нужно будет ручками работу со стеком реализовывать.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class function
{
public:
    virtual int priority()const=0;//приоритет операции
    virtual double calculate()const=0;//вычисление операции
protected:
    function*left=nullptr;//левый аргумент
    function*right=nullptr;//правый аргумент
};
class sum:public function
{
public:
    int priority()const{return 1;}
    double calculate()const{return left->calculate()+right->calculate();}
};
0
Fulcrum_013
721 / 746 / 73
Регистрация: 14.12.2014
Сообщений: 5,913
Завершенные тесты: 3
05.07.2015, 19:53 #5
по поводу ошибки - а символы в std::string точно с 0 нумеруются на не с 1? по ANSI стандарту на строки в первом (0-вом) символе длина а нумерация с 1.
0
Мизантроп_Лол
13 / 13 / 2
Регистрация: 26.02.2013
Сообщений: 285
Завершенные тесты: 1
05.07.2015, 19:55  [ТС] #6
Fulcrum_013, а можно ссылочку на описание алгоритма? А то я знаю только этот и рекурсивный спуск (но читал что он не очень эффективный).
0
Renji
1921 / 1319 / 298
Регистрация: 05.06.2014
Сообщений: 3,779
05.07.2015, 19:55 #7
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
по поводу ошибки - а символы в std::string точно с 0 нумеруются на не с 1?
Точно. Размер строки хранится отдельно и может превышать 255 (в один char не влезет).
0
Мизантроп_Лол
13 / 13 / 2
Регистрация: 26.02.2013
Сообщений: 285
Завершенные тесты: 1
05.07.2015, 19:58  [ТС] #8
Fulcrum_013,
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
по поводу ошибки - а символы в std::string точно с 0 нумеруются на не с 1? по ANSI стандарту на строки в первом (0-вом) символе длина а нумерация с 1.
Ну даже если и так, то почему ошибка вылетает еще до того, как что-либо сделалось? Т.е. я пытался в самом начале функции main поставить какой-нибудь вывод в консоль и бряк на него. Однако все равно вылетела эта ошибка и ничего более

Добавлено через 2 минуты
Renji,
Цитата Сообщение от Renji Посмотреть сообщение
У вас явно тот же потоковый ввод
В конечном счете приложение должно решать интегралы, а значит будет с графическим интерфейсом. А сейчас просто делаю модули, которые будут делать всю внутреннюю работу.

Насчет остального - подумаю. Интересные замечания, спасибо
0
Renji
1921 / 1319 / 298
Регистрация: 05.06.2014
Сообщений: 3,779
05.07.2015, 20:01 #9
Цитата Сообщение от Мизантроп_Лол Посмотреть сообщение
В конечном счете приложение должно решать интегралы, а значит будет с графическим интерфейсом.
Пофиг. stringstream не читает данные из консоли, а превращает заданный текст в поток. Так что ему без разницы какой у вас интерфейс.
C++
1
2
3
4
stringstream stream("1234 5678");//превратили текст в поток
int x,y;
stream>>x>>y;//прочитали текст из потока
cout<<x<<" "<<y<<endl;
0
Мизантроп_Лол
13 / 13 / 2
Регистрация: 26.02.2013
Сообщений: 285
Завершенные тесты: 1
05.07.2015, 20:04  [ТС] #10
Renji,
Цитата Сообщение от Renji Посмотреть сообщение
Через древо разбора функцию считать не удобнее будет?
Можно, пожалуйста, ссылочку на какую-то информацию по этой теме?

Добавлено через 1 минуту
Renji, насчет stringstream спасибо) Весьма полезно)
0
Fulcrum_013
721 / 746 / 73
Регистрация: 14.12.2014
Сообщений: 5,913
Завершенные тесты: 3
05.07.2015, 20:12 #11
Цитата Сообщение от Renji Посмотреть сообщение
Нафиг enum, нафиг switch по ним. Каждая элементарная операция описывается объектом function, в этом объекте лежит виртуальная функция calculate, которая эту элементарную операцию и считает.
Только элемент дерева можно и так создавать:
C++
1
    case PLUS: return [&, left, right]() { return left() + right(); };
Цитата Сообщение от Renji Посмотреть сообщение
Через древо разбора функцию считать не удобнее будет? По крайней мере, не нужно будет ручками работу со стеком реализовывать.
Главное распознавать справа налево. Тогда можно хоть дерево генерить не заморачиваясь с приоритетами, хоть сразу машкод.

Добавлено через 4 минуты
Цитата Сообщение от Мизантроп_Лол Посмотреть сообщение
а можно ссылочку на описание алгоритма?
Описание не читал Должно быть в стандарте С++,. Но смысл такой - если идешь с права налево, то операции просто сохраняют приоритет. Со скобками - закрывающаяся поместить аккумулятор в стек, открывающаяся - извлечь. по этой же причине и аргументы в стек С++ справа на лево вычисляет и засовывает.
0
Renji
1921 / 1319 / 298
Регистрация: 05.06.2014
Сообщений: 3,779
05.07.2015, 20:24 #12
Цитата Сообщение от Мизантроп_Лол Посмотреть сообщение
Можно, пожалуйста, ссылочку на какую-то информацию по этой теме?
Эм... Учебник математики? Дерево же дополняется в четыре строчки.
C++
1
2
3
4
5
6
7
8
9
10
11
12
void add_node(function*root,//корень дерева
    function*newnode//добавляемая операция
)
{
    //ищем самый правый узел дерева с приоритетом ниже добавляемой операции
    while(root->right&&root->right->priority()<newnode->priority())
        root=root->right;
    //правый аргумент найденного узла захватывает новая операция
    newnode->left=root->right;
    //и сама становится этим аргументом
    root->right=newnode;
}
В корне дерева - элемент-заглушка с наименьшим возможным приоритетом. Просто чтоб не заморачиваться случаем "а вдруг дерево пустое". Дальше читаем операции по одной и пихаем в дерево. Считая что переменные это тоже такие операции, но с максимальным приоритетом (считаются самыми первыми).
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
Главное распознавать справа налево. Тогда можно хоть дерево генерить не заморачиваясь с приоритетами, хоть сразу машкод.
Было 2*2+2. Прочитали справа налево - вышло 2+2*2. Ну и чем это помогло? Проигнорируем приоритет операций и скажем что результат - восемь, а не шесть?
0
Fulcrum_013
721 / 746 / 73
Регистрация: 14.12.2014
Сообщений: 5,913
Завершенные тесты: 3
05.07.2015, 20:29 #13
Цитата Сообщение от Мизантроп_Лол Посмотреть сообщение
В конечном счете приложение должно решать интегралы, а значит будет с графическим интерфейсом.
Значит удобнее с деревьями, а время парсинга все равно ничтожно мало по сравнению с временем вычисления. Делов тогда на час. Делал как то для интегралов. Идешь справа на лево, считаешь скобки. Если нашел оператор а скобок 0 то создаешь узел, в месте оператора делишь строку пополам и отдаешь половинки парсеру, результат заносишь в правый и левы ноды узла. Одна фича - надо удалять лишние скобки (a+2) к примеру - надо сначала убрать скобки а потом отдавать парсеру. Если операторов и скобок нет, проверяешь выражение на литерал или имя переменной. Примерно таким же макаром функции - т.е. если перед первой слева скобкой только букоффки - то это имя функции.
0
Мизантроп_Лол
13 / 13 / 2
Регистрация: 26.02.2013
Сообщений: 285
Завершенные тесты: 1
05.07.2015, 21:05  [ТС] #14
Renji, можно тогда пошаговый пример для выражения "x - 2 * ((1 / x) + (x / 3))". А то я не совсем понял, как оно делается
0
Renji
1921 / 1319 / 298
Регистрация: 05.06.2014
Сообщений: 3,779
05.07.2015, 21:29 #15
Цитата Сообщение от Мизантроп_Лол Посмотреть сообщение
Renji, можно тогда пошаговый пример для выражения "x - 2 * ((1 / x) + (x / 3))". А то я не совсем понял, как оно делается
Ну так дерево на бумажке нарисуйте. Исходное состояние:
корень

прочитали x, закинули
корень
 \
  x

прочитали минус, закинули
корень
 \
  -
 / \
x  пусто

прочитали 2, закинули
корень
 \
  -
 /  \
x   2

прочитали *, закинули
корень
 \
  -
 /  \
x   *
   / \
  2  пусто

Для скобок делаем рекурсивный вызов парсера.
корень
 \
  -
 /  \
x   *
   / \
  2  выражение в скобках

Итого, новая операция пихается вправо, так чтоб не нарушать приоритет операций (у минуса приоритет ниже чем у умножения, значит он остается выше). А что она там выпихнула - становится ее левым аргументом.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.07.2015, 21:29
Привет! Вот еще темы с ответами:

Вычисления математических выражений - C++
Это что выделено красным я не понимаю что с меня там хотят посмотрите у меня программе такое есть? &quot;реакцию программы на некорректны...

Программирование математических выражений в C++ - C++
Составить программу для вычисления значения функции F при указанных значениях аргументов и вывода значений аргументов и функций на экран...

Разбор математических выражений - C++
Добрый день, нуждаюсь в вашей помощи. Написал код программы для решения определённого уравнения методом половинного деления. Необходимо...

Анализатор математических выражений - C++
Всем привет. Я начинающий программист, там где я учусь, задали написать анализатор математических выражений. Я посмотрел в яндексе, гугле -...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
05.07.2015, 21:29
Ответ Создать тему
Опции темы

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