25 January 2009

Вычисление значения выражения

Algorithms
В продолжение поста Компилятор выражений. По просьбам читающих. Специально для michurin

Есть много способов вычислить значение выражения мне больше всего нравится метод с двумя стеками.
Нравится за его элегантность и простоту реализации.

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

Мы будем идти слева на право, добавляя операнды в один стек, а операции в другой. При каждом добавлении новой операции мы будем пытаться вытолкнуть из стека старые, руководствуясь приоритетами операций. (важно заметить, что тут как раз — таки и можно извратиться и сделать всё в 1 стеке, но мы будем придерживаться классики)

Так как слова Operator и Operand очень похожи, то вместо Operator мы будем использовать Function.
Стек Операндов будет называться Q
Стек Операторов W

Простой пример:
2 + 2 * 3 — 4
  1. Q.Push(2) Добавляем в стек Q операнд 2
  2. W.Push(+) Добавляем в стек W операцию +
  3. Q.Push(2)
  4. W.Push(*). Сейчас в W у нас находятся операции + и *. Так как у + приоритет выше, то * не может вытолкнуть его из стека.
  5. Q.Push(3)
  6. W.Push(-)
    у – приоритет выше чем у *, а значит, мы вытолкнем *. Для этого мы возьмём 2 последних операнда а на их место поставим результат операции A-B.
    B <- Q.pop()
    A <- Q.pop()
    Q.push(A - B)
    так мы будем повторять пока не наткнемся на операцию, которую не сможем вытолкнуть.
  7. В итоге у нас останется Q = {8, 4} и W={-}
    обычно, чтобы не разругивать последний шаг, всё выражение берется в скобки и последняя скобка выталкивает все оставшиеся операции.
  8. Q = {4} и W={}

Для примера возьмем операции + — * / и взятие в скобки.
у * и / приоритет будет равен 1
у + и – будет равен 2
у открывающейся скобки приоритет -1 и она никого не выталкивает.
Закрывающаяся скобка выталкивает все операции до первой открывающейся.

Пример: 2 + 1 – 6 / (1 + 2)
Рассмотрим пример по шагам:
  1. Q.push(2)
    Q = {2}
    W = { }
  2. W.push(+)
    Q = {2}
    W = {+}
  3. Q.push(1)
    Q = {2, 1}
    W = {+}
  4. W.push(-)
    у операций + и – приоритет равный, следовательно выталкиваем +
    Q = {3}
    W = {-}
  5. Q.push(6)
    Q = {3, 6}
    W = {-}
  6. W.push( / )
    Q = {3, 6}
    W = {-, /}
  7. W.push( ( )
    открывающаяся скобка никого не выталкивает, а просто добавляет себя в стек операций
    Q = {3, 6}
    W = {-, /, (}
  8. Q.push(1)
    Q = {3, 6, 1}
    W = {-, /, (}
  9. W.push(+)
    открывающуюся скобку может вытолкнуть только закрывающаяся. ничего не делаем.
    Q = {3, 6, 1}
    W = {-, /, (, +}
  10. Q.push(2)
    Q = {3, 6, 1, 2}
    W = {-, /, (, +}
  11. W.push( ) )
    Закрывающаяся скобка выталкивает все операции до первой открывающейся
    такая операция почти всегда одна (зависит от реализации)
    Q = {3, 6, 3}
    W = {-, /}
  12. Вот на этом шаге мы или сами разруливаем концовку или изначально оборачиваем выражение в круглые скобки, чтобы вытолкнуть все оставшиеся операции
    Q = {3, 2, 3}
    W = {-, /}
  13. Q = {1}
    W = {}
    результатом будет последнее число в стеке. Если там больше чем 1 число – значит, мы неправильно написали алгоритм или получили на вход кривое выражение.

Чтобы не заморачиваться с унарными операциями мы воспользуемся тем, что любую унарную можно превратить в бинарную. к примеру, добавить в качестве второго операнда единицу (нейтральный элемент)
т.е. вместо (-2) у нас будет (0 – 2)

Алгоритм на С#:

public static double Calc(string s)
{
s = '(' + s + ')';
Stack<double> Operands = new Stack<double>();
Stack<char> Functions = new Stack<char>();
int pos = 0;
object token;
object prevToken = 'Ы';

do
{
token = getToken(s, ref pos);
// разрливаем унарный + и -
if (token is char && prevToken is char &&
// если эту сточку заменить на (char)prevToken != ')' &&
// то можно будет писать (2 * -5) или даже (2 - -4)
// но нужно будет ввести ещё одну проверку так, как запись 2 + -+-+-+2 тоже будет работать :)
(char)prevToken == '(' &&
((char)token == '+' || (char)token == '-'))
Operands.Push(0); // Добавляем нулевой элемент

if (token is double) // Если операнд
{
Operands.Push((double)token); // то просто кидаем в стек
}
// в данном случае у нас только числа и операции. но можно добавить функции, переменные и т.д. и т.п.
else if (token is char) // Если операция
{
if ((char)token == ')')
{
// Скобка - исключение из правил. выталкивает все операции до первой открывающейся
while (Functions.Count > 0 && Functions.Peek() != '(')
popFunction(Operands, Functions);
Functions.Pop(); // Удаляем саму скобку "("
}
else
{
while (canPop((char)token, Functions)) // Если можно вытолкнуть
popFunction(Operands, Functions); // то выталкиваем

Functions.Push((char)token); // Кидаем новую операцию в стек
}
}
prevToken = token;
}
while (token != null);

if (Operands.Count > 1 || Functions.Count > 0)
throw new Exception("Ошибка в разборе выражения");

return Operands.Pop();
}

private static void popFunction(Stack<double> Operands, Stack<char> Functions)
{
double B = Operands.Pop();
double A = Operands.Pop();
switch (Functions.Pop())
{
case '+': Operands.Push(A + B);
break;
case '-': Operands.Push(A - B);
break;
case '*': Operands.Push(A * B);
break;
case '/': Operands.Push(A / B);
break;
}
}

private static bool canPop(char op1, Stack<char> Functions)
{
if (Functions.Count == 0)
return false;
int p1 = getPriority(op1);
int p2 = getPriority(Functions.Peek());

return p1 >= 0 && p2 >= 0 && p1 >= p2;
}

private static int getPriority(char op)
{
switch (op)
{
case '(':
return -1; // не выталкивает сам и не дает вытолкнуть себя другим
case '*': case '/':
return 1;
case '+': case '-':
return 2;
default:
throw new Exception("недопустимая операция");
}
}

private static object getToken(string s, ref int pos)
{
readWhiteSpace(s, ref pos);

if (pos == s.Length) // конец строки
return null;
if (char.IsDigit(s[pos]))
return Convert.ToDouble(readDouble(s, ref pos));
else
return readFunction(s, ref pos);
}

private static char readFunction(string s, ref int pos)
{
// в данном случае все операции состоят из одного символа
// но мы можем усложнить код добавив == && || mod div и ещё чегонить
return s[pos++];
}

private static string readDouble(string s, ref int pos)
{
string res = "";
while (pos < s.Length && (char.IsDigit(s[pos]) || s[pos] == '.'))
res += s[pos++];

return res;
}

// Считывает все проблемы и прочие левые символы.
private static void readWhiteSpace(string s, ref int pos)
{
while (pos < s.Length && char.IsWhiteSpace(s[pos]))
pos++;
}


* This source code was highlighted with Source Code Highlighter.


Это элементарный пример, который поддерживает всего 4 операции. Но его очень легко дополнить операциями && || ^ & | div mod просто задав им приоритет и написав реализацию.

Можно добавить переменные. Этим же алгоритмом можно строить и деревья. При том, деревья будут максимально вычисленные. т.е постоянные ветки (не содержащие переменных) можно будет вычисляться заранее.

Очень легко добавляется оператор запятая.
(2, 4 + 5, 4) превратится в массив {2, 9, 4}

Функции F(x1, x2, …, xn) это унарная операция над массивом {x1, x2, …, xn}

Если пост понравился, в следующем напишу о том, как я делал небольшой функциональный язык и объектно-ориентированный язык.
Tags:алгоритмыразбор выражений
Hubs: Algorithms
+51
41.6k 65
Comments 36