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

Обратная Польская Нотация - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.93
turtLe
3 / 3 / 2
Регистрация: 11.11.2009
Сообщений: 41
16.10.2010, 18:56     Обратная Польская Нотация #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
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
#include <iostream>
using namespace std;
 
struct stack{
    char key;
    stack *next;
}*top=NULL,*p=new stack;
 
void push(char S)
{
    if(p!=NULL)
    {
        p->key=S;
        p->next=top;
        top=p;
    }
    else return;
 
}
 
char pop()
{
    char S;
    stack *p=new stack;
    p=top;
    S=p->key;
    top=p->next;
    delete p;
    return S;
}
 
int main()
{
    char Sinput[21];
    char Soutput[21];
    int k=0,n=0,Q;
    p=NULL;
    cout<<"Enter a mathematical expression: ";
    gets(Sinput);
    cout<<"\n";
    Q=strlen(Sinput);
    while(Q>k)
   {
        if ((Sinput[k]>=0)||(Sinput[k]<=9))
            {
                Soutput[n]=Sinput[k];
                k++;
                n++;
            }
        switch(Sinput[k])
        {
            
            case '(':
            {
                push(Sinput[k]);
                k++;
                break;
            }
            case ')':
            {
                    while(pop()!='(')
                    {
                        Soutput[n]=pop();
                        n++;
                    }
                    pop();break;
            }
             case '+':
             {
                 if((p->key=='-')||(p->key=='+'))
                 {
                     Soutput[n]=pop();
                     n++;
                 }
                 push(Sinput[k]);
                 k++;
                 break;
             }
             case '-':
             {
                 if((p->key=='-')||(p->key=='+'))
                 {
                     Soutput[n]=pop();
                     n++;
                 }
                 push(Sinput[k]);
                 k++;break;
             }
             case '*':
             {
                 if((p->key=='*')||(p->key=='^'))
                 {
                     Soutput[n]=pop();
                     n++;
                 }
                 push(Sinput[k]);
                 k++;break; 
             }
             case '/':
             {
                 if((p->key=='^'))
                 {
                     Soutput[n]=pop();
                     n++;
                 }
                 push(Sinput[k]);
                 k++;break;
             }
             case '^':
             {
                 push(Sinput[k]);
                 k++;
                 break;
             }
        }
        k++;
        n++;
    }
 
    if (Q==k)
        while(p!=NULL)
        {
            Soutput[n]=pop();
            n++;
        }
 
    cout<<"\n";
    for(int i=0;i<=strlen(Soutput);i++)
    cout<<Soutput[i]<<" ";
system("pause");
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.10.2010, 18:56     Обратная Польская Нотация
Посмотрите здесь:

обратная польская запись. C++
Обратная польская запись C++
Обратная польская запись C++
Обратная польская запись C++
C++ Обратная польская запись
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
16.10.2010, 19:36     Обратная Польская Нотация #2
Цитата Сообщение от turtLe Посмотреть сообщение
Пытался реализовать ОПН....ничего не вышло
поконкретней можно?

Вот простой калькулятор, осуществляющий перевод выражения и вычисление в ОПН

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

Опять же, недавно лабораторную делал - калькулятор логических выражений. Поддерживает операции & (И), | (ИЛИ), !(НЕ), >, <, =. Есть константы true и false. Этот пример сделан поудачней предыдущего
bracket.hpp
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
#ifndef BRACKET_HPP
#define BRACKET_HPP
 
#include "token.hpp"
 
namespace my
{
    /*
     * Перечисление - тип скобки
     */
    enum bracket_type
    {
        b_left, // Открывающая скобка
        b_right // Закрывающая скобка
    };
 
    /*
     * Абстрактный класс - скобка
     * Предок - my::token
     */
    class bracket: public token
    {
 
    public:
 
        bracket(bracket_type type);
 
        bracket_type btype() const;
 
        ~bracket() = 0;
 
    protected:
 
        bracket_type m_btype; // Тип скобки
    };
 
    /*
     * Класс - открывающая скобка
     * Предок - my::bracket
     */
    class lbracket: public bracket
    {
 
    public:
 
        lbracket();
    };
 
    /*
     * Класс - закрывающая скобка
     * Предок - my::bracket
     */
    class rbracket: public bracket
    {
 
    public:
 
        rbracket();
    };
} // namespace my
 
#endif // BRACKET_HPP

calculator.hpp
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
#ifndef CALCULATOR_HPP
#define CALCULATOR_HPP
 
#include "token.hpp"
#include "pstack.hpp"
#include "pqueue.hpp"
 
#include <string>
 
 
namespace my
{
    /*
     * Класс, предоставляющий интерфейс
     * для вычисления выражений в инфиксной нотации
     */
    class calculator
    {
 
    public:
 
        calculator();
 
        /*
         * Метод вычисляет и возвращает значение выражения, записанного в rhs;
         * если произошла ошибка, возвращается false,
         * а errOccured становится равным true
         */
        bool operator ()(const std::string& rhs, bool& errOccured);
 
    private:
 
        /*
         * Метод осуществляет синтаксический анализ:
         * производит перевод исходного выражения, записанного
         * в инфиксной нотации, в набор токенов, хранящихся в очереди m_pqRPN
         * в обратной польской (постфиксной) нотации
         */
        void fromInfixToPostfix();
 
        /*
         * Метод осуществляет лексический разбор строки на токены,
         * с каждым вызовом вычленяя очередной токен из исходной строки и
         * помещяя его в очередь m_pqRPN
         */
        token* getToken();
 
        /*
         * Вспомогательный функции для лексического разбора строки
         */
        bool isOperator(char c);
        token* getOperator(char c);
        int getInteger();
        token* getBoolean();
 
        std::string         m_sExpr; // Исходная строка
        my::pqueue          m_pqRPN; // Очередь лексем в постфиксной нотации
        my::pstack          m_psStk; // Стек для вычисления
        size_t              m_nIndex; // Индекс текущего элемента строки
    };
} // namespace my
 
#endif // CALCULATOR_HPP

operand.hpp
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
#ifndef OPERAND_HPP
#define OPERAND_HPP
 
#include "token.hpp"
 
namespace my
{
    /*
     * Перечисление - тип операнда
     */
    enum operand_type
    {
        op_integer, // Целочисленный операнд
        op_boolean  // Булев операнд
    };
 
    /*
     * Абстрактный класс - операнд
     * Предок - my::token
     */
    class operand: public token
    {
 
    public:
 
        operand(operand_type type);
 
        ~operand() = 0;
 
        operand_type otype() const;
 
    protected:
 
        operand_type m_otype; // Тип операнда
    };
 
    /*
     * Класс - целочисленный операнд
     * Предок - my::operand
     */
    class integer: public operand
    {
 
    public:
 
        explicit integer(int value);
 
        int value() const;
 
    private:
 
        int m_nValue; // Хранящееся значение
    };
 
    /*
     * Класс - булев операнд
     * Предок - my::operand
     */
    class boolean: public operand
    {
 
    public:
 
        explicit boolean(bool value);
 
        bool value() const;
 
    private:
 
        bool m_bValue; // Хранящееся значение
    };
} // namespace my
 
#endif // OPERAND_HPP

operator.hpp
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
#ifndef OPERATOR_HPP
#define OPERATOR_HPP
 
#include "token.hpp"
#include "pstack.hpp"
 
namespace my
{
    /*
     * Перечисление - приоритет оператора
     */
    enum operator_priority
    {
        pr1,
        pr2,
        pr3
    };
 
    /*
     * Абстрактный класс - оператор
     * Предок - my::token
     */
    class operators: public token
    {
 
    public:
 
        operators(operator_priority prior);
 
        ~operators() = 0;
 
        virtual void operator ()(pstack&); // Вычисление оператора
 
        operator_priority priority() const;
 
    private:
 
        operator_priority m_pprior; // Приоритет оператора
    };
 
    /*
     * Классы-операторы
     * Предок - my::operators
     *
     * equal_op     -   '=' ("Равно")
     * greater_op   -   '>' ("Больше")
     * lesser_op    -   '<' ("Меньше")
     * or_op        -   '|' ("Или")
     * and_op       -   '&' ("И")
     * not_op       -   '!' ("Не")
     */
    class equal_op: public operators
    {
 
    public:
 
        equal_op();
 
        void operator ()(pstack& rhs);
    };
 
    class greater_op: public operators
    {
 
    public:
 
        greater_op();
 
        void operator ()(pstack& rhs);
    };
 
    class lesser_op: public operators
    {
 
    public:
 
        lesser_op();
 
        void operator ()(pstack& rhs);
    };
 
    class or_op: public operators
    {
 
    public:
 
        or_op();
 
        void operator ()(pstack& rhs);
    };
 
    class and_op: public operators
    {
 
    public:
 
        and_op();
 
        void operator ()(pstack& rhs);
    };
 
    class not_op: public operators
    {
 
    public:
 
        not_op();
 
        void operator ()(pstack& rhs);
    };
} // namespace my
 
#endif // OPERATOR_HPP

pqueue.hpp
#ifndef PQUEUE_HPP
#define PQUEUE_HPP

#include <cstdlib>

#include "token.hpp"

/*
* Очередь, хранящая динамические указатели на тип my::token
*/
namespace my
{
class pqueue
{

public:

pqueue();
~pqueue();

void push(token* pTok);
token* pop();
token* head();

bool empty() const;

void clear();

private:

struct node
{
token* ptData;
node* pnNext;

node(token* pTok)
: ptData(pTok), pnNext(NULL) {}
};

node* m_pnHead;
node* m_pnTail;
};
} // namespace my

#endif // PQUEUE_HPP

pstack.hpp
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
#ifndef PSTACK_HPP
#define PSTACK_HPP
 
#include <cstdlib>
 
#include "token.hpp"
 
/*
 * Стек, хранящий динамические указатели на тип my::token
 */
namespace my
{
    class pstack
    {
 
    public:
 
        pstack();
        ~pstack();
 
        void push(token* pTok);
        token* pop();
        token* top();
 
        bool empty() const;
 
        void clear();
 
    private:
 
        struct node
        {
            token*  ptData;
            node*   pnNext;
 
            node(token* pTok)
                : ptData(pTok), pnNext(NULL) {}
        };
 
        node* m_pnTop;
    };
} // namespace my
 
#endif // PSTACK_HPP

token.hpp
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
#ifndef TOKEN_HPP
#define TOKEN_HPP
 
namespace my
{
    /*
     * Структура-исключение
     */
    struct token_exception
    {
        char    token_id;
 
        token_exception(char id);
    };
 
    /*
     * Перечисление - тип токена
     */
    enum token_type
    {
        t_operand,  // Операнд
        t_operator, // Оператор
        t_bracket   // Скобка
    };
 
    /*
     * Абстрактный класс - токен
     */
    class token
    {
 
    public:
 
        token(token_type type);
 
        virtual ~token() = 0;
 
        token_type ttype() const;
 
    protected:
 
        token_type m_ttype; // Тип токена
    };
} // namespace my
#endif // TOKEN_HPP

bracket.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "bracket.hpp"
 
namespace my
{
    bracket::bracket(bracket_type type)
        : token(t_bracket), m_btype(type) {}
 
    bracket_type bracket::btype() const
    {
        return m_btype;
    }
 
    bracket::~bracket()
    {
    }
 
    lbracket::lbracket()
        : bracket(b_left) {}
 
    rbracket::rbracket()
        : bracket(b_right) {}
} // namespace my

calculator.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
#include "calculator.hpp"
 
#include <cstdlib>
#include <iostream>
 
#include "operator.hpp"
#include "operand.hpp"
#include "bracket.hpp"
 
namespace my
{
    calculator::calculator()
        : m_nIndex(0) {}
 
    bool calculator::operator ()(const std::string& rhs, bool& errOccured)
    {
        errOccured = false;
        bool retval;
        m_nIndex = 0;
        m_sExpr = rhs;
        // Перевод символов исходной строки в нижний регистр
        for(std::string::iterator it = m_sExpr.begin();
            it != m_sExpr.end();
            ++it)
            *it = tolower(*it);
        /*
         * Очищаем стек и очередь от токенов, которые могли остаться после
         * прошлых неудачных вычислений
         */
        m_pqRPN.clear();
        m_psStk.clear();
        try
        {
            // Перевод выражение в постфиксную нотацию
            fromInfixToPostfix();
            // Если очередь токенов пуста - выбрасываем исключение
            if(m_pqRPN.empty())
                throw token_exception('\0');
 
            // Производим вычисление согласно алгоритму
            while(!m_pqRPN.empty())
            {
                token* tok = m_pqRPN.pop();
 
                if(tok->ttype() == t_operand)
                    m_psStk.push(tok);
 
                else if(tok->ttype() == t_operator)
                {
                    dynamic_cast<operators*>(tok)->operator ()(m_psStk);
                    delete tok;
                }
            }
            // Выталкиваем токен, в котором должен храниться результат
            token* tok = m_psStk.pop();
            // Проверяем, что этот токен - именно булев операнд
            if((tok->ttype() != t_operand) ||
               ((tok->ttype() == t_operand) &&
                (dynamic_cast<operand*>(tok)->otype() != op_boolean)))
                throw token_exception('\n');
            retval = dynamic_cast<boolean*>(tok)->value();
            delete tok;
            // Если в стеке еще остались токены, то выбрасываем исключение
            if(!m_psStk.empty())
                throw token_exception('\n');
        }
        // Обработка исключительных ситуаций
        catch(const token_exception& e)
        {
            if(isOperator(e.token_id))
                    std::cerr << "Неожиданная ошибка возле токена \'"
                            << e.token_id << "\'" << std::endl;
            else
                switch(e.token_id)
                {
                case '(':
                case ')':
                    std::cerr << "Ошибка: ожидалась парная скобка для \'"
                        << e.token_id << "\'" << std::endl;
                    break;
 
                case '\0':
                    std::cerr << "Ошибка: попытка вычислить пустое выражение"
                            << std::endl;
                    break;
 
                case ' ':
                    std::cerr << "Ошибка: пустые скобочные конструкции запрещены"
                            << std::endl;
                    break;
 
                case '\n':
                    std::cerr << "Ошибка: не удалось разобрать выражение"
                            << std::endl;
                    break;
 
                default:
                    std::cerr << "Ошибка: неизвестная лексема \'" << e.token_id
                            << "\'" << std::endl;
                }
 
            std::cerr << "Невозможно вычислить выражение из-за возникших ошибок"
                    << std::endl << std::endl;
            errOccured = true;
            retval = false;
        }
        return retval;
    }
 
    void calculator::fromInfixToPostfix()
    {
        // Перевод выражения в постфиксную нотацию согласно алгоритму
        while(token* tok = getToken()) // Вычленяем очередной токен
        {
            // ... и осуществляем синтаксический анализ
            if(tok->ttype() == t_operand)
                m_pqRPN.push(tok);
            else if((tok->ttype() == t_bracket) &&
                    (dynamic_cast<bracket*>(tok)->btype() == b_left))
                m_psStk.push(tok);
            else if((tok->ttype() == t_bracket) &&
                    (dynamic_cast<bracket*>(tok)->btype() == b_right))
            {
                if(m_psStk.empty())
                    throw token_exception(')');
                if(m_psStk.top()->ttype() == t_bracket)
                    throw token_exception(' ');
                token* mvtok;
                while((mvtok = m_psStk.pop())->ttype() != t_bracket)
                {
                    m_pqRPN.push(mvtok);
                    if(m_psStk.empty())
                        throw token_exception(')');
                }
                delete mvtok;
            }
            else if(tok->ttype() == t_operator)
            {
                operator_priority pr = dynamic_cast<operators*>(tok)->priority();
                while((!m_psStk.empty()) &&
                      (m_psStk.top()->ttype() != t_bracket) &&
                      (pr <= dynamic_cast<operators*>(m_psStk.top())->priority()))
                    m_pqRPN.push(m_psStk.pop());
 
                m_psStk.push(tok);
            }
        }
        while(!m_psStk.empty())
        {
            if(m_psStk.top()->ttype() != t_operator)
                throw token_exception('(');
            m_pqRPN.push(m_psStk.pop());
        }
    }
 
    token* calculator::getToken()
    {
        if(m_nIndex == m_sExpr.size())
            return NULL;
        if(isOperator(m_sExpr[m_nIndex]))
            return getOperator(m_sExpr[m_nIndex++]);
        if(m_sExpr[m_nIndex] == ' ')
        {
            ++m_nIndex;
            return getToken();
        }
        if(m_sExpr[m_nIndex] == '(')
        {
            ++m_nIndex;
            return new lbracket;
        }
        if(m_sExpr[m_nIndex] == ')')
        {
            ++m_nIndex;
            return new rbracket;
        }
        if(isdigit(m_sExpr[m_nIndex]))
        {
            int result = getInteger();
            return new integer(result);
        }
        if(m_sExpr[m_nIndex] == '-')
        {
            if(((++m_nIndex) == m_sExpr.size()) || (!isdigit(m_sExpr[m_nIndex])))
                throw token_exception('-');
            int result = -1 * getInteger();
            return new integer(result);
        }
        if((m_sExpr[m_nIndex] == 't') || (m_sExpr[m_nIndex] == 'f'))
            return getBoolean();
        else
            throw token_exception(m_sExpr[m_nIndex]);
    }
 
    token* calculator::getBoolean()
    {
        static std::string _true_("true");
        static std::string _false_("false");
        if(m_sExpr.find(_true_, m_nIndex) != std::string::npos)
        {
            m_nIndex += _true_.size();
            return new boolean(true);
        }
        if(m_sExpr.find(_false_, m_nIndex) != std::string::npos)
        {
            m_nIndex += _false_.size();
            return new boolean(false);
        }
        throw token_exception(m_sExpr[m_nIndex]);
    }
 
    int calculator::getInteger()
    {
        int result = m_sExpr[m_nIndex] - '0';
        while(((++m_nIndex) != m_sExpr.size()) && isdigit(m_sExpr[m_nIndex]))
            result = result * 10 + (m_sExpr[m_nIndex] - '0');
        return result;
    }
 
    bool calculator::isOperator(char c)
    {
        switch(c)
        {
        case '<':
        case '>':
        case '=':
        case '&':
        case '|':
        case '!':
 
            return true;
 
        default:
 
            return false;
        }
    }
 
    token* calculator::getOperator(char c)
    {
        switch(c)
        {
        case '<':
 
            return new lesser_op;
 
        case '>':
 
            return new greater_op;
 
        case '=':
 
            return new equal_op;
 
        case '&':
 
            return new and_op;
 
        case '|':
 
            return new or_op;
 
        default:
            return new not_op;
        }
    }
} // namespace my

operand.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
#include "operand.hpp"
 
namespace my
{
    operand::operand(operand_type type)
        : token(t_operand), m_otype(type) {}
 
    operand::~operand()
    {
    }
 
    operand_type operand::otype() const
    {
        return m_otype;
    }
 
    integer::integer(int value)
        : operand(op_integer), m_nValue(value) {}
 
    int integer::value() const
    {
        return m_nValue;
    }
 
    boolean::boolean(bool value)
        : operand(op_boolean), m_bValue(value) {}
 
    bool boolean::value() const
    {
        return m_bValue;
    }
} // namespace my

operator.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
#include "operator.hpp"
#include "operand.hpp"
 
#include <stdexcept>
#include <iostream>
 
namespace my
{
    operators::operators(operator_priority prior)
        : token(t_operator), m_pprior(prior) {}
 
    operators::~operators()
    {
    }
 
    void operators::operator ()(pstack&)
    {
    }
 
    operator_priority operators::priority() const
    {
        return m_pprior;
    }
 
    equal_op::equal_op()
        : operators(pr2) {}
 
    void equal_op::operator ()(pstack& rhs)
    {
        try
        {
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("equal: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_integer)
                throw std::runtime_error(
                        "equal: неверный тип аргумента 2 (ожидалось число)");
            integer* op2 = dynamic_cast<integer*>(rhs.pop());
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("equal: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_integer)
                throw std::runtime_error(
                        "equal: неверный тип аргумента 1 (ожидалось число)");
            integer* op1 = dynamic_cast<integer*>(rhs.pop());
            rhs.push(new boolean((op1->value()) == (op2->value())));
            delete op1;
            delete op2;
        }
        catch(std::runtime_error err)
        {
            std::cerr << err.what() << std::endl;
            throw(token_exception('='));
        }
    }
 
    greater_op::greater_op()
        : operators(pr2) {}
 
    void greater_op::operator ()(pstack& rhs)
    {
        try
        {
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("greater: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_integer)
                throw std::runtime_error(
                        "greater: неверный тип аргумента 2 (ожидалось число)");
            integer* op2 = dynamic_cast<integer*>(rhs.pop());
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("greater: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_integer)
                throw std::runtime_error(
                        "greater: неверный тип аргумента 1 (ожидалось число)");
            integer* op1 = dynamic_cast<integer*>(rhs.pop());
            rhs.push(new boolean((op1->value()) > (op2->value())));
            delete op1;
            delete op2;
        }
        catch(std::runtime_error err)
        {
            std::cerr << err.what() << std::endl;
            throw(token_exception('>'));
        }
    }
 
    lesser_op::lesser_op()
        : operators(pr2) {}
 
    void lesser_op::operator ()(pstack& rhs)
    {
        try
        {
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("lesser: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_integer)
                throw std::runtime_error(
                        "lesser: неверный тип аргумента 2 (ожидалось число)");
            integer* op2 = dynamic_cast<integer*>(rhs.pop());
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("lesser: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_integer)
                throw std::runtime_error(
                        "lesser: неверный тип аргумента 1 (ожидалось число)");
            integer* op1 = dynamic_cast<integer*>(rhs.pop());
            rhs.push(new boolean((op1->value()) < (op2->value())));
            delete op1;
            delete op2;
        }
        catch(std::runtime_error err)
        {
            std::cerr << err.what() << std::endl;
            throw(token_exception('<'));
        }
    }
 
    or_op::or_op()
        : operators(pr1) {}
 
    void or_op::operator ()(pstack& rhs)
    {
        try
        {
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("or: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_boolean)
                throw std::runtime_error(
                        "or: неверный тип аргумента 2 (ожидалось булево число)");
            boolean* op2 = dynamic_cast<boolean*>(rhs.pop());
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("or: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_boolean)
                throw std::runtime_error(
                        "or: неверный тип аргумента 1 (ожидалось булево число)");
            boolean* op1 = dynamic_cast<boolean*>(rhs.pop());
            rhs.push(new boolean((op1->value()) || (op2->value())));
            delete op1;
            delete op2;
        }
        catch(std::runtime_error err)
        {
            std::cerr << err.what() << std::endl;
            throw(token_exception('|'));
        }
    }
 
    and_op::and_op()
        : operators(pr1) {}
 
    void and_op::operator ()(pstack& rhs)
    {
        try
        {
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("and: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_boolean)
                throw std::runtime_error(
                        "and: неверный тип аргумента 2 (ожидалось булево число)");
            boolean* op2 = dynamic_cast<boolean*>(rhs.pop());
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("and: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_boolean)
                throw std::runtime_error(
                        "and: неверный тип аргумента 1 (ожидалось булево число)");
            boolean* op1 = dynamic_cast<boolean*>(rhs.pop());
            rhs.push(new boolean((op1->value()) && (op2->value())));
            delete op1;
            delete op2;
        }
        catch(std::runtime_error err)
        {
            std::cerr << err.what() << std::endl;
            throw(token_exception('&'));
        }
    }
 
    not_op::not_op()
        : operators(pr3) {}
 
    void not_op::operator ()(pstack& rhs)
    {
        try
        {
            if(rhs.top()->ttype() != t_operand)
                throw std::runtime_error("not: получен не аргумент");
            if(dynamic_cast<operand*>(rhs.top())->otype() != op_boolean)
                throw std::runtime_error(
                        "not: неверный тип аргумента (ожидалось булево число)");
            boolean* op = dynamic_cast<boolean*>(rhs.pop());
            rhs.push(new boolean(!(op->value())));
            delete op;
        }
        catch(std::runtime_error err)
        {
            std::cerr << err.what() << std::endl;
            throw(token_exception('!'));
        }
    }
} // namespace my

pqueue.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
#include "pqueue.hpp"
 
#include <stdexcept>
 
namespace my
{
    pqueue::pqueue()
        : m_pnHead(NULL), m_pnTail(NULL) {}
 
    pqueue::~pqueue()
    {
        clear();
    }
 
    void pqueue::clear()
    {
        while(m_pnHead)
        {
            node* delNode = m_pnHead;
            m_pnHead = m_pnHead->pnNext;
            delete delNode->ptData;
            delete delNode;
        }
        m_pnTail = NULL;
    }
 
    void pqueue::push(token *pTok)
    {
        node* newNode = new node(pTok);
        if(!m_pnTail)
            m_pnHead = newNode;
        else
            m_pnTail->pnNext = newNode;
        m_pnTail = newNode;
    }
 
    token* pqueue::pop()
    {
        if(!m_pnHead)
            throw std::runtime_error("pqueue: ошибка удаления - очередь пуста");
        node* delNode = m_pnHead;
        m_pnHead = m_pnHead->pnNext;
        if(!m_pnHead)
            m_pnTail = NULL;
        token* retval = delNode->ptData;
        delete delNode;
        return retval;
    }
 
    token* pqueue::head()
    {
        if(!m_pnHead)
            throw std::runtime_error("pqueue: ошибк чтения - очередь пуста");
        return m_pnHead->ptData;
    }
 
    bool pqueue::empty() const
    {
        return m_pnHead == NULL;
    }
} // namespace my

pstack.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
#include "pstack.hpp"
 
#include <stdexcept>
 
namespace my
{
    pstack::pstack()
        : m_pnTop(NULL) {}
 
    pstack::~pstack()
    {
        clear();
    }
 
    void pstack::clear()
    {
        while(m_pnTop)
        {
            node* delNode = m_pnTop;
            m_pnTop = m_pnTop->pnNext;
            delete delNode->ptData;
            delete delNode;
        }
    }
 
    void pstack::push(token* pTok)
    {
        node* newNode = new node(pTok);
        if(m_pnTop)
            newNode->pnNext = m_pnTop;
        m_pnTop = newNode;
    }
 
    token* pstack::pop()
    {
        if(!m_pnTop)
            throw std::runtime_error("pstack: ошибка удаления - стек пуст");
        node* delNode = m_pnTop;
        m_pnTop = m_pnTop->pnNext;
        token* retval = delNode->ptData;
        delete delNode;
        return retval;
    }
 
    token* pstack::top()
    {
        if(!m_pnTop)
            throw std::runtime_error("pstack: ошибка чтения - стек пуст");
        return m_pnTop->ptData;
    }
 
    bool pstack::empty() const
    {
        return m_pnTop == NULL;
    }
} // namespace my

token.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "token.hpp"
 
namespace my
{
    token_exception::token_exception(char id)
        : token_id(id) {}
 
    token::token(token_type type)
        : m_ttype(type) {}
 
    token::~token()
    {
    }
 
    token_type token::ttype() const
    {
        return m_ttype;
    }
} // namespace my


main.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
#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <iterator>
 
#include "calculator.hpp"
 
int main(int argc, char *argv[])
{
    if(argc == 1)
    {
        std::cerr << "Использование: " << *argv
                << " ВЫРАЖЕНИЕ [...]" << std::endl;
        return EXIT_FAILURE;
    }
    std::vector<std::string> exprVec;
    exprVec.reserve(argc - 1);
    // Помещаем выражения, переданный как аргументы, в вектор
    for(size_t i = 1; i < argc; ++i)
        exprVec.push_back(std::string(argv[i]));
 
    my::calculator calculate;
    size_t errCnt = 0;
    // Вычисляем каждое выражение
    for(std::vector<std::string>::const_iterator it = exprVec.begin();
        it != exprVec.end();
        ++it)
    {
        std::cout << "Вычисляем выражение \'" << *it << "\':" << std::endl;
        bool err;
        bool result = calculate(*it, err);
        if(!err) // Если не возникло ошибок, печатаем результат
            std::cout << "Результат: " << result << " (" << std::boolalpha
                    << result << ")" << std::noboolalpha << std::endl
                    << std::endl;
        else
            ++errCnt;
    }
    std::cout << "Всего выражений: " << (argc - 1) << std::endl;
    std::cout << "Успешно вычислено: " << (argc - 1 - errCnt) << std::endl;
    std::cout << "Не удалось вычислить: " << errCnt << std::endl;
    return EXIT_SUCCESS;
}

Выражения вводятся как параметры командной строки
turtLe
3 / 3 / 2
Регистрация: 11.11.2009
Сообщений: 41
16.10.2010, 19:42  [ТС]     Обратная Польская Нотация #3
Nameless One, может он и простой,но мне все равно сложно разобраться в вашей
C++
1
void calculator::fromInfixToPostfix()
.
Я хотел бы,чтобы мне помогли разобраться в моих ошибках.
С алгоритмом вроде не напутал, брал описание с wikipedia.
На выходе вообще что-то непонятное получается,как-то работа с char у меня неправильно что ли осуществлена...
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
16.10.2010, 19:54     Обратная Польская Нотация #4
Цитата Сообщение от turtLe Посмотреть сообщение
С алгоритмом вроде не напутал, брал описание с wikipedia.
Вот хотя бы здесь:
пока…
… (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…
… (если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…
… выталкиваем верхние элементы стека в выходную строку;
Вот это уже и не выполняется

PS. Там же есть пример реализации на Паскале, если моя программа кажется сложной
turtLe
3 / 3 / 2
Регистрация: 11.11.2009
Сообщений: 41
16.10.2010, 22:50  [ТС]     Обратная Польская Нотация #5
Nameless One, помоги разобраться с ф-циями push и pop
что-то стэк у меня не получается(
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
16.10.2010, 23:03     Обратная Польская Нотация #6
turtLe, используй
C++
1
#include <stack>
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.10.2010, 11:05     Обратная Польская Нотация
Еще ссылки по теме:

Польская инверсная нотация C++
C++ Обратная Польская Запись
Обратная польская нотация через структуру C++

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

Или воспользуйтесь поиском по форуму:
turtLe
3 / 3 / 2
Регистрация: 11.11.2009
Сообщений: 41
17.10.2010, 11:05  [ТС]     Обратная Польская Нотация #7
PointsEqual, не прокатит,не должно быть этого в моей лабе надо все ручками писать.

Добавлено через 11 часов 0 минут
C++
1
2
3
4
5
6
7
8
9
10
string pop()
{
    string S;
    stack *tmp=new stack;
    tmp=p;
    S+=tmp->data;
    p=tmp->next;
    delete tmp;
    return S;
}
в чем ошибка?
Yandex
Объявления
17.10.2010, 11:05     Обратная Польская Нотация
Ответ Создать тему
Опции темы

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