Здравствуйте, TerryKath, Вы писали:

TK>Помогите, пожалуйста! Никак не могу придумать, как написать эту рекурсивную процедуру...
Почитай про метод Дейкстры (преобразование выражения в обратную польскую нотацию):
http://algolist.manual.ru/maths/misc/revpn.php

Никак не могу сообразить, как решить эту задачу:
Формулу вида
<формула>::=<терминал>|(<формула><знак><формула>)
<знак>::= + | -| /1 *
<терминал>::= 0|1|2|3|4|5|6|7|8|9
можно представить в виде двоичного дерева с элементами типа char. Написать
программу, которая используя рекурсивную подпрограмму, по формуле строит
дерево-формулу.

То есть, например, если дана формула 2*1+2*3-3, то дерево будет иметь такой вид:
................+
............./.....\
............*.......-
.........../\......./\
..........2..1....*..3
................../\
.................2..3

Помогите, пожалуйста! Никак не могу придумать, как написать эту рекурсивную процедуру...

Здравствуйте, TerryKath, Вы писали:
TK>Помогите, пожалуйста! Никак не могу придумать, как написать эту рекурсивную процедуру...
Строить дерево — это идея правильная.
Строить нужно
1. с хвоста. Пример:
2-2+2
2. Причем вначале искать знаки с наименьшим приоритетом. Пример:
2*2-2

Здравствуйте, TerryKath, Вы писали:
TK>Помогите, пожалуйста! Никак не могу придумать, как написать эту рекурсивную процедуру...
Строить дерево — это идея правильная.
Строить нужно
1. с хвоста. Пример:
2-2+2
2. Причем вначале искать знаки с наименьшим приоритетом. Пример:
2*2-2

P.S. Janus глючит, если таких сообщений будет 2 — не обесудьте

Здравствуйте, TerryKath, Вы писали:

TK>Помогите, пожалуйста! Никак не могу придумать, как написать эту рекурсивную процедуру...

Вообще говоря, это задача построить парсер операторной грамматики. За подробностями — велкам то Ахо,Хопкрофт,Ульман, гугл и т.п.

Парсер представляет собой стековый автомат. Стек можно хранить как отдельную структуру, либо совместить со стеком вызовов. Вот первое место для рекурсии.
Парсер последовательно читает входную строку и выполняет над каждым символом и своим стеком некие действия. Этот итерационный процесс можно заменить на эквивалентную концевую рекурсию (а в функциональных языках — не только можно, но и нужно). Это второе место.

Дальнейшие объяснения хорошо бы приводить с комментариями на каком-то конкретном языке программирования. Поэтому за тобой "выбор оружия". Затем продолжим.

Здравствуйте, TerryKath, Вы писали:

TK>То есть, например, если дана формула 2*1+2*3-3, то дерево будет иметь такой вид:
TK>................+
TK>............./.....\
TK>............*.......-
TK>.........../\......./\
TK>..........2..1....*..3
TK>................../\
TK>.................2..3

TK>Помогите, пожалуйста! Никак не могу придумать, как написать эту рекурсивную процедуру...
Вот минут за 10 накатал, особо не тестировал, но идея должна быть ясна

struct Tree 
{
    virtual ~Tree() {};
};

struct Node : Tree
{
    char op_;
    Tree * left_, * right_;
    Node(char op, Tree * left, Tree * right) : op_(op), left_(left), right_(right) {}
    ~Node()
    {
        delete left_;
        delete right_;
    }
};

struct Leaf : Tree
{
    int number_;
    Leaf(char * &s) : number_(0)
    {
        while(*s == ' ' || *s == '\t' || *s == '\r' || *s == '\n')
            ++s;
        int sign = 1;
        while(*s == '+' || *s == '-')
        {
            if(*s == '-')
                sign *= -1;
            ++s;
        }
        while(*s >= '0' && *s <= '9')
            (number_ *= 10) += *s++ - '0';
    }
};

Tree * MulDiv(char * &s)
{
    Tree * tree = new Leaf(s);
    for(;;)
        if(*s == '*' || *s == '/')
        {
            char op = *s++;
            tree = new Node(op, tree, new Leaf(s));
        }
        else if(*s == ' ' || *s == '\t' || *s == '\r' || *s == '\n')
            ++s;
        else
            return tree;
}

Tree * PlusMinus(char * &s)
{
    Tree * tree = MulDiv(s);
    for(;;)
        if(*s == '-' || *s == '+')
        {
            char op = *s++;
            tree = new Node(op, tree, MulDiv(s));
        }
        else if(*s == ' ' || *s == '\t' || *s == '\r' || *s == '\n')
            ++s;
        else
            return tree;
}

Tree * Parse(char * s)
{
    return PlusMinus(s);
}

int main()
{
    char s[] = "10 + 20 * 30";
    Tree * tree = Parse(s);
    delete tree;
}