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

Алгоритм сортировочной станции(вычисление по обратной польской записи). - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.70
usatik
0 / 0 / 0
Регистрация: 27.11.2011
Сообщений: 4
27.11.2011, 06:22     Алгоритм сортировочной станции(вычисление по обратной польской записи). #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
#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
const int SIZE = 256;
 
class stack{
    int p;
    int data[SIZE];
public:
    stack(){
        for (int i = 0; i < SIZE; i++)
            data[i] = 0;
        p = 0;
    }
    int pop(){
        p--;
        return data[p];
    }
    void push(int num){
        data[p] = num;
        p++;
    }
}
 
int iGetNum(stack &num, int Dig){
    int razr = 1;
    int number = 0;
    for (int i = 0; i < Dig; i++){
        number += num.pop() * razr;
        razr *= 10;
    }
    return number;
}
 
int iPower(int n, int k){
    int c = 1;
    while (k != 1){
        if (k % 2 == 0){
            k /= 2;
            n *= n;
        }
        else{
            k--;
            c *= n;
        }
    }
    return n * c;
}
 
int main()
{
    ifstream input("input.txt");
    ofstream output("output.txt");
    char cTmp;
    stack num;
    stack data;
    int iTmp = 0;
    int iAop = 0;
    int iBop = 0;
    int iDigits = 0;//количество считанных цифр числа
    while (!input.eof()){
        input >> cTmp;
        if (cTmp == ' ') continue;
        iTmp = (int)(cTmp - '0');
        while (iTmp => 0 && iTmp <= 9){//пока идут цифры, записывать из в стек для цифр
            num.push(iTmp);
            input >> cTmp;
            iDigits++;
        }
        if (iDigits == 1)
            data.push(num.pop());
        else
            data.push(iGetNum(num, iDigits)); // запихиваем в стек число
        iDigits = 0;
        if (cTmp == '+'){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop + iBop);
        }
        if (cTmp == '-'){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop - iBop);
        }
        if (cTmp == '*'){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop * iBop);
        }
        if (cTmp == '/'){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop / iBop);
        }
        if (cTmp == '^'){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iPower(iAop, iBop));
        }
    }
    output << data.pop();
    input.close();
    output.close();
    return 0;
}
Задумывалось, что он будет считать выражение уже записанное в обратной польской нотации.
Компилиться он отказывается, выдавая следующие:

Код
26: new types may not be defined in a return type
26: extraneous 'int' ignored
     in function 'stack iGetNum(stack&, int)';
33: conversion from 'int' to non-scalar type 'stack' requested
     in function 'int main()'
66: expected primary-expression before '>' token
74: no matching function for coll to 'stack::push(stack)'
note: candidates are: void stack::push(int)
Среда Dev-C++.
Вобщем я что-то там нахимичил и не могу разобраться с этими ошибками.
Помогите пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.11.2011, 06:22     Алгоритм сортировочной станции(вычисление по обратной польской записи).
Посмотрите здесь:

C++ Организовать вычисление выражения, используя алгоритм польской записи
Вычисление сильных компонент орграфа. Алгоритм Габова. C++
C++ Дан алгоритм нахождения обратной матрицы. По нему хочу написать код. Но непонятно по какому методу он работает.
Вычисление выражения записанного в виде обратной польской записи используя бинарное дерево C++
C++ Вычислить значение выражения в обратной польской записи с использованием стека
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
27.11.2011, 06:28     Алгоритм сортировочной станции(вычисление по обратной польской записи). #2
после определения класса поставь точку с запятой
usatik
0 / 0 / 0
Регистрация: 27.11.2011
Сообщений: 4
27.11.2011, 08:34  [ТС]     Алгоритм сортировочной станции(вычисление по обратной польской записи). #3
У меня нет слов (:
Мб, раз я уже создал тему, сделаете замечания по реализации?
А то не могу избавиться от чувства, что я как-то кривовато пишу.

Добавлено через 1 час 5 минут
У меня не работает считывание чисел состоящих более чем из одного разряда, решил на него пока забить и попробовать с одноразрядными числами. Внезапно обнаружил что и для них не работает.
Подскажите что не правильно?
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
int main()
{
    ifstream input("input.txt");
    ofstream output("output.txt");
    char cTmp;
    stack num;
    stack data;
    int iTmp = 0;
    int iAop = 0;
    int iBop = 0;
    int iDigits = 0;
    while (!input.eof()){
        input >> cTmp;
        if (cTmp == ' ') continue;
        if (cTmp == '+'){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop + iBop);
        }
        if (cTmp == '-'){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop - iBop);
        }
        if (cTmp == '*'){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop * iBop);
        }
        if (cTmp == '/'){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop / iBop);
        }
        if (cTmp == '^'){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iPower(iAop, iBop));
        }
        iTmp = (int)(cTmp - '0');
        if (iTmp >= 0 && iTmp <= 9){
            /*while (cTmp != ' '){
                iTmp = (int)(cTmp - '0');
                num.push(iTmp);
                iDigits++;
                input >> cTmp;
            }
            data.push(iGetNum(num, iDigits));
            iDigits = 0;*/
            data.push(iTmp);
        }
    }
    output << data.pop();
    input.close();
    output.close();
    return 0;
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
27.11.2011, 14:48     Алгоритм сортировочной станции(вычисление по обратной польской записи). #4
Цитата Сообщение от usatik Посмотреть сообщение
Внезапно обнаружил что и для них не работает.
что значит "не работает"? Не компилируется? Или считает неправильно? А ты учитываешь, что деление у тебя целочисленное?
usatik
0 / 0 / 0
Регистрация: 27.11.2011
Сообщений: 4
27.11.2011, 14:56  [ТС]     Алгоритм сортировочной станции(вычисление по обратной польской записи). #5
Именно неправильно считает.
Во входных данных у меня нет деления.
Выдает или ноль или -1.
Сам не могу понять от чего это зависит.
Пытался в отладчике лазить, толи непривычная среда, толи там не обошлось без магии.
Считывание чисел работает корректно, но как дело доходит до знака арифметич действия он как положено достает два предыдущих операнда, а дальше непостижимым образом прыгает в функцию push, после этого я перестаю понимать что происходит(он что-то там еще считывает, хотя файл должен был уже кончиться, а в переменных операндов непонятные значения появляются).
Самому аж страшно как такое смог написать ):
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
27.11.2011, 15:32     Алгоритм сортировочной станции(вычисление по обратной польской записи). #6
Ну вот например (токены разделены пробельными символами, проверки неверного ввода нет):
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
#include <iostream>
#include <sstream>
#include <string>
#include <stack>
#include <stdexcept>
 
bool is_operator(const std::string& token)
{
    static const std::string ops[] = {"+", "-", "*", "/"};
 
    for(size_t i = 0; i < sizeof(ops) / sizeof(*ops); ++i)
    if(token == ops[i])
        return true;
 
    return false;
}
 
int add(int op1, int op2)
{
    return op1 + op2;
}
 
int sub(int op1, int op2)
{
    return op1 - op2;
}
 
int mul(int op1, int op2)
{
    return op1 * op2;
}
 
int div_(int op1, int op2) throw(std::runtime_error)
{
    if(op2 == 0)
    throw std::runtime_error("Division by zero");
 
    return op1 / op2;
}
 
int pow_(int op1, int op2) throw(std::runtime_error)
{
    if(op2 < 0)
    throw std::runtime_error("Raising to negative power: not yet implemented");
 
    int result = 1;
 
    while(op2 > 0)
    {
    if(!(op2 & 1))
    {
        op2 >>= 1;
        op1 *= op1;
    } else {
        --op2;
        result *= op1;
    }
    }
 
    return result;
}
 
typedef int (*BIN_OP) (int, int);
 
BIN_OP bin_op(const std::string token) throw(std::runtime_error)
{
    if(token == "+")
    return add;
    if(token == "-")
    return sub;
    if(token == "*")
    return mul;
    if(token == "/")
    return div_;
    if(token == "^")
    return pow_;
 
    throw std::runtime_error("No such binary operator: " + token);
    
    return NULL;
}
 
int next_number(std::stack<int>& stack) throw(std::runtime_error)
{
    if(stack.empty())
    throw std::runtime_error("Empty stack");
 
    int result = stack.top();
    stack.pop();
 
    return result;
}
 
int main(int argc, char* argv[])
{
    if(argc == 1)
    {
    std::cerr << "Usage: eval EXPR [EXPR...]" << std::endl;
    return EXIT_FAILURE;
    }
    
    
    for(int i = 1; i < argc; ++i)
    {
    std::cout << argv[i] << " = ";
        
    std::istringstream input(argv[i]);
    std::stack<int> stack;
    std::string token;
 
    try
    {
        while(input >> token)
        {
        if(is_operator(token))
        {
            int op2 = next_number(stack);
            int op1 = next_number(stack);
            
            stack.push(bin_op(token)(op1, op2));
        } else {
            stack.push(atoi(token.c_str()));
        }
        }
 
        int result = next_number(stack);
        
        if(!stack.empty())
        throw std::runtime_error("extra data provided");
 
        std::cout << result << std::endl;
    }
 
    catch(const std::exception& e)
    {
        std::cerr << "[Error: "
              << e.what() << "]" << std::endl;
    }
    }
    
    return EXIT_SUCCESS;
}
Код
[nameless@desktop cpp]$ ./eval
Usage: eval EXPR [EXPR...]
[nameless@desktop cpp]$ ./eval \
> "3 5 + 2 - 3 / 10 ^" \
> "3 /" \
> "5 2 7 + 9 - /" \
> "0 4 5 6 - + ^" \
> "42 25 14 39 - + ^ 5 *"
> "8 9 15 - ^"
3 5 + 2 - 3 / 10 ^ = 1024
3 / = [Error: Empty stack]
5 2 7 + 9 - / = [Error: Division by zero]
0 4 5 6 - + ^ = 0
42 25 14 39 - + ^ 5 * = 5
8 9 15 - ^ = [Error: Raising to negative power: not yet implemented]
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2011, 15:21     Алгоритм сортировочной станции(вычисление по обратной польской записи).
Еще ссылки по теме:

Написание калькулятора в Обратной Польской Записи C++
Вычитание, умножение, вычисление обратной матрицы C++
C++ Вычисление обратной величины произведения в С++

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

Или воспользуйтесь поиском по форуму:
usatik
0 / 0 / 0
Регистрация: 27.11.2011
Сообщений: 4
28.11.2011, 15:21  [ТС]     Алгоритм сортировочной станции(вычисление по обратной польской записи). #7
Все работает, большое спасибо.
В результате копипаста различной степени наглости вышло следующие:
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
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int SIZE = 256;
 
class stack{
    int p;
    int data[SIZE];
public:
    stack(){
        for (int i = 0; i < SIZE; i++)
            this->data[i] = 0;
        this->p = 0;
    }
    int pop(){
        this->p--;
        return this->data[p];
    }
    void push(int num){
        this->data[p] = num;
        p++;
    }
};
 
int power(int n, int k){
    int c = 1;
    while (k != 1){
        if (k % 2 == 0){
            k /= 2;
            n *= n;
        } else {
            k--;
            c *= n;
        }
    }
    return n * c;
}
 
int main()
{
    ifstream input("input.txt");
    ofstream output("output.txt");
    string token;
    stack data;
    int iAop = 0;
    int iBop = 0;
    while (input >> token){
        if (token == "+"){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop + iBop);
            continue;
        }
        if (token == "-"){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop - iBop);
            continue;
        }
        if (token == "*"){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop * iBop);
            continue;
        }
        if (token == "/"){
            iBop = data.pop();
            iAop = data.pop();
            data.push(iAop / iBop);
            continue;
        }
        if (token == "^"){
            iBop = data.pop();
            iAop = data.pop();
            data.push(power(iAop, iBop));
            continue;
        }
        data.push(atoi(token.c_str()));
    }
    output << data.pop();
    input.close();
    output.close();
    return 0;
}
Yandex
Объявления
28.11.2011, 15:21     Алгоритм сортировочной станции(вычисление по обратной польской записи).
Ответ Создать тему
Опции темы

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