Ещё раз РЕКУРСИЯ

[Sirik]

Никто не знает, как с помощью рекурсии решить, например, такое выражение: (2+4)/3 ???
Помню где было, но, как всегда, не помню где.
Очень надо, помогите

[alibek]

Если имеется какое-то конкретное выражение, то не вижу смысла.
А так выглядит примерно таким образом:

Исходное выражение: (2+4)/3
Проводится парсинг (ищется выражение в скобках). Если найдено (это будет 2+4), то рекурсивно вызывается процедура с найденным аргументом (2+4).
Если выражений в скобках больше нет, то вычисляется выражение и результат возвращается.

[Sirik]

За идею спасибо.
Но, я написал только пример. На самом деле всё гараздо сложнее.
Вот ещё один пример: ( ( 2 + 4 ) / ( 3 + 8 ) ) * ( 4 + 5 )
Заранее ни числа, ни само выражение не известы.
Я где видел контрол, который это всё делает, вот только не могу найти.

[alibek]

Для ( ( 2 + 4 ) / ( 3 + 8 ) ) * ( 4 + 5 ) будет так:

1. ((2+4)/(3+8))*(4+5)
2. ((2+4)/(3+8)) и (4+5)
2.1.1. (2+4)/(3+8)
2.1.2. (2+4) и (3+8)
2.1.2.1.1. (2+4) => 6
2.1.2.2.1. (3+8) => 11
2.1.3. =6/11
2.2.1. (4+5) => 9
3. 6/11*9


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

[Sirik]

Спасибо, теперь болле понятнее.
Но у меня есть ещё один вопрос, как при использовании рекурсии сохранять данные?
Я во всём этом ух-ты как запутался. Если есть примерчик, было бы здорово...

[Sirik]

Да, кстати, только что нашёл приме того что мне надо.
Но как он работает я не понимаю

[alibek]

Могу даже каркас кода дать (приблизительный).

Код: Выделить всё

Function Eval(ByVal Expression As String) As Double
'Expression = "( ( 2 + 4 ) / ( 3 + 8 ) ) * ( 4 + 5 )"
Expression = Replace(Expression, " ", vbNullString)
Expression = Replace(Expression, ",", ".")

'Op1 и Op2 - операнды (Double)
'Op - операция (умножение, деление, сложение, вычитание и т.п.)

While Len(Expression) > 0
  If InStr(Expression, "(") > 0 Then
    'P1 - позиция открывающейся скобки, _(_(2+4)/(3+8))
    'P2 - позиция закрывающейся скобки, ((2+4)/(3+8)_)_
    res = Eval(Mid$(Expression, P1+1, P2-P1-1)
    Expression = Mid$(Expression, 1, P1-1) & Trim$(Str$(res)) & Mid$(Expression, P2+1)
  Else
    'P0 - позиция оператор с наивысшим приоритетом, 2+4_/_11
    'P1 - позиция первого операнда, 2+_4_/11
    'P2 - позиция второго операнда, 2+4/_11_
    'L0, L1, L2 - соответственно, длина оператора или операнда
    'Если в выражении нет операндов, то P0 = 0
    If P0 = 0 Then
      Op1 = Val(Expression)
      Expression = vbNullString
    Else
      Op = Mid$(Expression, P0, L0)
      Op1 = Val(Mid$(Expression, P1, L1)
      Op2 = Val(Mid$(Expression, P2, L2)
      res = Eval(Mid$(Expression, P1, P2+L2-1)
      Expression = Mid$(Expression, 1, P1-1) & Mid$(Expression, P2+L2)
    End If
  End If
WEnd

Select Case Op
  Case vbNullString
    Eval = Op1
  Case "*"
    Eval = Op1 * Op2
  Case "+"
    Eval = Op1 + Op2
...
End Select
End Function

[Sirik]

2 alibek Спасибо большое, помогло!!!

[Sirik]

alibek, ты можешь сказать, что в моём коде неправильно:

Код: Выделить всё

Private Sub Command1_Click()
  MsgBox Rec(1)
End Sub

Function Rec(i As Integer) As Integer
  If i > 10 Then Exit Function
  i = i + 1
  Rec = Rec(i)
End Function


Я только начинаю работать с рекурсией, и опыта нет. Вернее сказть, я не знаю как с ней работать. Подскажи

[alibek]

А о какой ошибке он говорит?
Я бы написал так:

Код: Выделить всё

Function Rec(ByVal I As Integer) As Integer
If I > 10 Then
  Rec = 10
  Exit Funtion
End If
Rec = Rec(I+1)
End Function

Код: Выделить всё

'Intermediate
?Rec(11)

Думаю, что либо напрасно ты передаешь I по значению (ты ведь его же и изменяешь в коде). И еще, когда ты делаешь выход из процедуры, она возвращает 0. Т.е. когда управление с нее при I>10 возвращается в процедуру, которая ее вызвала (она же при I=10), то получается Rec=0. И так по цепочке этот ноль и отобразится в исходной процедуре, которая вызывала Rec.

[Aqualung]

Э... Если речь идет о симуляции компиляции (чего это я сказал? ), то, сначала, желательно перевести всю формулу в обратную польскую запись: "операнд1 операнд 2 оператор". Да и синтаксис неплохо бы проверить.

[Daz]

За идею спасибо.
Но, я написал только пример. На самом деле всё гараздо сложнее.
Вот ещё один пример: ( ( 2 + 4 ) / ( 3 + 8 ) ) * ( 4 + 5 )
Заранее ни числа, ни само выражение не известы.
Я где видел контрол, который это всё делает, вот только не могу найти.

Может это тебе поможет ?