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

C++

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

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

06.03.2015, 18:59. Просмотров 544. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.03.2015, 18:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсивное вычисление постфиксного выражения без стека(!) (C++):

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

Вычисление выражения, введенного в Edit - C++ Builder
Здравствуйте форумчане) У меня большая проблема( хочу сделать калькулятор для простых действий +-/* сам калькулятор готов но только на одно...

Организовать проверку сбалансированности скобок при вводе выражения с помощью стека - Visual C++
Нужно:Организовать проверку сбалансированности скобок при вводе выражения с помощью стека. Скобки могут быть разные- (), , {}.

Преобразование выражения из постфиксного в префиксное представление - C++
Помогите написать программу. Разработать программу преобразования выражения из постфиксного в префиксное представление.

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

Рекурсивное вычисление x!-sin(x) - C++
помогите пожалуйста написать программу s=x!-sin(x)

3
Dennis Ritchie
547 / 139 / 29
Регистрация: 27.07.2014
Сообщений: 2,445
07.03.2015, 10:18 #2
Цитата Сообщение от ShinaZin Посмотреть сообщение
Напишите рекурсивную программу, вычисляющую значение постфиксного выражения.
А формат входных данных какой имеет вид? Два числа типа int и арифметический знак? Или сложное выражение со скобками?
0
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: работает только для целых чисел, хотя исправлять не много там для работы с дробями. Ну и нет "защиты от дураков", кому надо - допилят
0
Dennis Ritchie
547 / 139 / 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;
1
07.03.2015, 10:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.03.2015, 10:45
Привет! Вот еще темы с ответами:

Рекурсивное вычисление НОК - C++
return (b &lt; 1 ? (b ? NOK(b, a % b) : a) : (a / -NOK(-b, -a % b) * b)); // РЕБЯТА ОБЪЯСНИТЕ ПОЖАЛУЙСТА ЭТУ СТРОЧКУ. СРОЧНО НУЖНО!!!

Рекурсивное вычисление функции - C++
Функция f(n) определяется рекурсивно: f(2*n)=f(n),f(2*n+1)=f(n)+f(n+1), f(0)=0,f(1)=1.написать программу вычисляющую функцию f(n)

Рекурсивное вычисление суммы. - C++
Здравствуйте! Помогите пожалуйста. Написать программу, рекурсивно вычисляющую сумму. Найти сумму ряда с точностью Eps, общий член...

Рекурсивное вычисление цепной дроби - C++
Народ помогите, как сделать рекурсивную функцию для этого y(n) = , n - число ступеней.


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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