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

C++

Войти
Регистрация
Восстановить пароль
 
ShinaZin
0 / 0 / 0
Регистрация: 03.04.2014
Сообщений: 13
#1

Рекурсивное вычисление постфиксного выражения без стека(!) - C++

06.03.2015, 18:59. Просмотров 497. Ответов 3
Метки нет (Все метки)

Имеется такие интересное задание: Напишите рекурсивную программу, вычисляющую значение постфиксного выражения. Знаю, что выражения в постфиксной форме обычно вычисляются с помощью стека, а выражения в префиксной форме удобно вычислять с помощью рекурсивной функции. Но на основе этих знаний не получается придумать нормальный рабочий алгоритм, который позволил бы вычислить постфиксное выражение. Есть идея хранить результат последнего действия хранить во временной переменной (как первый операнд) и вызывать рекурсивную функцию, для него и следующего вычисленного операнда, но в итоге руки все равно тянутся написать все на стеке. Может есть другие идеи у кого-то?

Добавлено через 6 минут
Кликните здесь для просмотра всего текста
Прошу удалить/перенести тему в соответствующий раздел, ибо в силу своей криворукости не смог этого сделать


Добавлено через 53 минуты
Пока ждал, придумал еще одно решение, которое более менее работает - рассматривать постфиксное выражение как префиксное, но обрабатывать его с конца, а действия вычитания, возведения в степень и деления преобразовать для обратного порядка операндов. Пока еще не уверен, что работает все, но пару тестов код уже прошел удачно
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
#include <iostream>
#include <cstring>
 
using namespace std;    
float eval();
char str[255];
int i = 0;
 
int main(int argc, char *argv[]) 
{
    strcpy(str,argv[1]);//Чтение входной строки
    i = strlen(str)-1;//Индекс = индекс последний символ, который не '\0'
    cout<<eval()<<'\n';//Обработка
    return 0;
}
 
float eval()
{
    float x = 0;
    if (str[i] == '+')
    {
        i--;
        x=eval() + eval();
        return x;
    }
 
    if (str[i] == '*')
    {
        i--;
        x=eval() * eval();
        return x;
    }
    
    if (str[i] == '/')
    {
        i--;
        x=eval() / eval();
        return 1.0/x; //Обратное значение из-за обратного порядка
    }
    
    if (str[i] == '-')
    {
        i--;
        x=eval() - eval();
        return -1*x; //Обратное значение
    }
    if (str[i] == '^')
    {
        i--;
        int n,p,j, res=1;
        n=eval(); //Возводим число p
        p=eval(); //в степень n
        for(j=0;j<n;j++)
          res*=p;
        return res;
    }
    if((str[i] >= '0') && (str[i] <= '9'))
        x = (str[i--] - '0');
    return x;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.03.2015, 18:59     Рекурсивное вычисление постфиксного выражения без стека(!)
Посмотрите здесь:
Рекурсивное вычисление C++
Рекурсивное вычисление функции C++
Рекурсивное вычисление НОК C++
C++ Рекурсивное вычисление суммы.
Рекурсивное вычисление x!-sin(x) C++
Рекурсивное вычисление корня k-й степени C++
Рекурсивное и нерекурсивное вычисление функции C++
C++ Рекурсивное вычисление цепной дроби
C++ Рекурсивное вычисление значения функции
C++ Рекурсивное вычисление значения функции разложением в ряд Тейлора
C++ Напишите рекурсивное правило вычисления значения выражения
C++ Рекурсивное вычисление. Найти среднее арифметическое по двум частям массива

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dennis Ritchie
546 / 138 / 29
Регистрация: 27.07.2014
Сообщений: 2,445
07.03.2015, 10:18     Рекурсивное вычисление постфиксного выражения без стека(!) #2
Цитата Сообщение от ShinaZin Посмотреть сообщение
Напишите рекурсивную программу, вычисляющую значение постфиксного выражения.
А формат входных данных какой имеет вид? Два числа типа int и арифметический знак? Или сложное выражение со скобками?
ShinaZin
0 / 0 / 0
Регистрация: 03.04.2014
Сообщений: 13
07.03.2015, 10:32  [ТС]     Рекурсивное вычисление постфиксного выражения без стека(!) #3
Входная строка - массив символов, например 93+6-, для простоты считаем, что числа состоят из одной цифры, а разделителей (типа пробела) нет, это для варианта выше. Кстати, скобок в постфиксной записи я не припомню. А сам я уже написал вариант программы, который обрабатывает строки примерно такого вида: 27 90 - 110 + 2 ^
Вот он:
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
#include <iostream>
#include <cstring>
 
using namespace std;    
float eval();
char str[255];
int i = 0;
 
int main(int argc, char *argv[]) 
{
    if(argc==1) {
      cout<<"Input postfix string: "; gets(str);
  }
    else strcpy(str,argv[1]);//чтение строки из параметров запуска
    i = strlen(str)-1;//Индекс = последний символ, не '\0'
    cout<<str<<" = "<<eval()<<'\n';//вычисление выражения
    return 0;
}
 
float eval()
{
    float x = 0;
    while (str[i]==' ') i--;
 
    if (str[i] == '+')
    {
        i--;
        x=eval() + eval();
        return x;
    }
 
    if (str[i] == '*')
    {
        i--;
        x=eval() * eval();
        return x;
    }
    
    if (str[i] == '/')
    {
        i--;
        x=eval() / eval();
        return 1.0/x; //обратное значение, из-за обратного порядка вычисления
    }
    
    if (str[i] == '-')
    {
        i--;
        x=eval() - eval();
        return -1*x; //обратное значение
    }
    if (str[i] == '^')
    {
        i--;
        int n,p,j, res=1;
        n=eval();//возводим число p
        p=eval();//в степень n
        for(j=0;j<n;j++)
          res*=p;
        return res;
    }
    int w=1;//"вес" очередной цифры
    while((str[i] >= '0') && (str[i] <= '9')){
        x = x + (str[i--] - '0')*w;
        w*=10;
    }
        
    return x;
}
PS: работает только для целых чисел, хотя исправлять не много там для работы с дробями. Ну и нет "защиты от дураков", кому надо - допилят
Dennis Ritchie
546 / 138 / 29
Регистрация: 27.07.2014
Сообщений: 2,445
07.03.2015, 10:45     Рекурсивное вычисление постфиксного выражения без стека(!) #4
Цитата Сообщение от ShinaZin Посмотреть сообщение
хотя исправлять не много там для работы с дробями.
Может быть, поможет:
C++
1
2
3
4
5
6
7
8
9
10
11
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '-' || s[i] == '+')
    ++i;
double val = число до десятичной запятой, power;
if (s[i] == '.')
    ++i;
for (power = 1.0; isdigit(s[i]); ++i) {
    val = 10.0 * val + (s[i] - '0');
    power *= 10;
}
val = sign * val / power;
Yandex
Объявления
07.03.2015, 10:45     Рекурсивное вычисление постфиксного выражения без стека(!)
Ответ Создать тему
Опции темы

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