Я бы решил эту проблему, используя Reverse Poli sh Обозначение , где вы можете просто добавлять операторы и операнды в строку, учитывая некоторые простые правила.
Например, выражение 2 + (3 * 4) будет иметь значение 2 3 4 * + в обратной записи Poli sh. С другой стороны, (2 + 3) * 4 будет 2 3 + 4 *.
Если у нас уже есть частичное выражение, мы можем добавить операнд или оператор.
Добавление операнда всегда может быть готово и увеличит размер стека на 1. С другой стороны, добавление оператора уменьшает размер стека на 1 (удаляет два самых верхних операнда и добавляет результат) и поэтому может быть выполнено только если стек имеет как минимум две записи. В конце, чтобы сформировать правильное выражение, размер стека должен быть ровно 1.
Это мотивирует рекурсивную функцию со следующим интерфейсом:
getSubexpressions(remainingOperands, currentStackSize)
Функция возвращает список подвыражения, которые могут быть добавлены к частичному выражению с размером стека currentStackSize и использованием операндов remainingOperands.
Базовый случай этой рекурсивной функции - когда больше нет оставшихся операндов и размер стека равен 1 :
if remainingOperands = ∅ and currentStackSize = 1
return { "" }
В этом случае мы можем добавить в выражение только пустую строку.
Во всех остальных случаях нам нужно собрать набор подвыражений
subexpressions = { } // initialize an empty set
Если мы можем добавить оператор, мы можем просто добавить его:
if currentStackSize >= 2
for each possible operator o
subexpressions.add(o + getSubexpressions(remainingOperands, currentStackSize - 1))
Обозначение o + getSubexpressions(remainingOperands, currentStackSize - 1) является сокращением для конкатенации операнда o со всеми подвыражениями, возвращенными из вызова к getSubexpressions() .
Мы почти у цели. Последний оставшийся бит должен добавить потенциальные операнды:
for each o in remainingOperands
subexpressions.add(o + getSubexpressions(remainingOperands \ { o }, currentStackSize + 1))
Обозначение remainingOperands \ { o } обозначает разность наборов, т. Е. Набор оставшихся операндов без o.
Вот и все. В целом:
getSubexpressions(remainingOperands, currentStackSize)
if remainingOperands = ∅ and currentStackSize = 1
return { "" }
subexpressions = { } // initialize an empty set
if currentStackSize >= 2
for each possible operator o
subexpressions.add(o + getSubexpressions(remainingOperands, currentStackSize - 1))
for each o in remainingOperands
subexpressions.add(o + getSubexpressions(remainingOperands \ { o }, currentStackSize + 1))
return subexpressions
Этот рекурсивный вызов обычно будет иметь перекрывающиеся вызовы. Следовательно, вы можете использовать памятку для кэширования промежуточных результатов, а не пересчитывать их снова и снова.
Вот реализация концепции для проверки без памятки в C#. В частности, управление операндами может быть разработано более эффективно с более подходящими структурами данных:
static void Main(string[] args)
{
foreach (var expr in GetSubexpressions(new List<string> { "1", "2", "3" }, 0, new StringBuilder()))
{
Console.WriteLine(expr);
}
}
static char[] operators = { '+', '-', '*', '/' };
static IEnumerable<StringBuilder> GetSubexpressions(IList<string> remainingOperands, int currentStackSize, StringBuilder sb)
{
if (remainingOperands.Count() == 0 && currentStackSize == 1)
{
yield return sb;
yield break;
}
if(currentStackSize >= 2)
{
foreach (var o in operators)
{
sb.Append(o);
foreach (var expr in GetSubexpressions(remainingOperands, currentStackSize - 1, sb))
yield return expr;
sb.Remove(sb.Length - 1, 1);
}
}
for (int i = 0; i < remainingOperands.Count; ++i)
{
var operand = remainingOperands[i];
remainingOperands.RemoveAt(i);
sb.Append(operand);
foreach (var expr in GetSubexpressions(remainingOperands, currentStackSize + 1, sb))
yield return expr;
sb.Remove(sb.Length - operand.Length, operand.Length);
remainingOperands.Insert(i, operand);
}
}
Программа выводит следующий вывод:
12+3+
12-3+
12*3+
12/3+
12+3-
12-3-
12*3-
12/3-
12+3*
12-3*
12*3*
12/3*
12+3/
12-3/
12*3/
12/3/
123++
123-+
123*+
123/+
123+-
123--
123*-
123/-
123+*
123-*
123**
123/*
123+/
123-/
123*/
123//
13+2+
13-2+
13*2+
13/2+
13+2-
13-2-
13*2-
13/2-
13+2*
13-2*
13*2*
13/2*
13+2/
13-2/
13*2/
13/2/
132++
132-+
132*+
132/+
132+-
132--
132*-
132/-
132+*
132-*
132**
132/*
132+/
132-/
132*/
132//
21+3+
21-3+
21*3+
21/3+
21+3-
21-3-
21*3-
21/3-
21+3*
21-3*
21*3*
21/3*
21+3/
21-3/
21*3/
21/3/
213++
213-+
213*+
213/+
213+-
213--
213*-
213/-
213+*
213-*
213**
213/*
213+/
213-/
213*/
213//
23+1+
23-1+
23*1+
23/1+
23+1-
23-1-
23*1-
23/1-
23+1*
23-1*
23*1*
23/1*
23+1/
23-1/
23*1/
23/1/
231++
231-+
231*+
231/+
231+-
231--
231*-
231/-
231+*
231-*
231**
231/*
231+/
231-/
231*/
231//
31+2+
31-2+
31*2+
31/2+
31+2-
31-2-
31*2-
31/2-
31+2*
31-2*
31*2*
31/2*
31+2/
31-2/
31*2/
31/2/
312++
312-+
312*+
312/+
312+-
312--
312*-
312/-
312+*
312-*
312**
312/*
312+/
312-/
312*/
312//
32+1+
32-1+
32*1+
32/1+
32+1-
32-1-
32*1-
32/1-
32+1*
32-1*
32*1*
32/1*
32+1/
32-1/
32*1/
32/1/
321++
321-+
321*+
321/+
321+-
321--
321*-
321/-
321+*
321-*
321**
321/*
321+/
321-/
321*/
321//