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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ С++ и Ассемблерная вставка/чтение SPD ОЗУ http://www.cyberforum.ru/cpp/thread1389011.html
Добрый день форумчане, делаю программу на подобии CPU-Z, необходимо узнать тайминги и прочую информацию из SPD оперативной памяти. Нашел код Asssmbler на просторах интернета, но без понятия как его...
C++ Как сделать Game over в игре Здравствуйте, разрабатываю змейку через OpenGL на с++ и в принципе игра работает , но хотелось бы как то сделать что бы если змейка выползает за границы игрового поля выскакивала надпись или может... http://www.cyberforum.ru/cpp/thread1387920.html
C++ Блокировка мыши по оси y
Здравствуйте! Нужно решить задачу: Вычислять текущую позицию по оси y, и при нажатии ctrl(control)+1 блокировать мышь по этой оси, т.е чтоб y был равен всегда тому значению, которое было при...
C++ Парсер выражений
Здравствуйте, помогите пожалуйста написать простой парсер, для дальнейшей самостоятельной доработки под нужды. Ссылки на гугл и прочее не интересует, перерыл уже. мне нужно консольное приложение,...
C++ Топологическая сортировка http://www.cyberforum.ru/cpp/thread1386242.html
Есть алгоритм, реализация с помощью обхода в глубину: http://rain.ifmo.ru/cat/view.php/vis/graph-general/topological-sort-2007/algorithm boolean topological_sort(){ boolean Cycle; ...
C++ Урок геометрии, масштабирование изображений Задача: Есть картинка 100x100 px на которой нарисован смайлик необходимо наложить этот смайлик на другие фотографии, размер которых заранее неизвестен. (Я в курсе как программно наложить одну... подробнее

Показать сообщение отдельно
ShinaZin
0 / 0 / 0
Регистрация: 03.04.2014
Сообщений: 13

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

06.03.2015, 18:59. Просмотров 534. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru