Baks Jan 25 2009 at 17:03

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

7 min

48K

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

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

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

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

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

Простой пример:
2 + 2 * 3 — 4


Q.Push(2) Добавляем в стек Q операнд 2
W.Push(+) Добавляем в стек W операцию +
Q.Push(2)
W.Push(*). Сейчас в W у нас находятся операции + и *. Так как у + приоритет выше, то * не может вытолкнуть его из стека.
Q.Push(3)
W.Push(-)

у – приоритет выше чем у *, а значит, мы вытолкнем *. Для этого мы возьмём 2 последних операнда а на их место поставим результат операции A-B.

B <- Q.pop()

A <- Q.pop()

Q.push(A - B)

так мы будем повторять пока не наткнемся на операцию, которую не сможем вытолкнуть.
В итоге у нас останется Q = {8, 4} и W={-}

обычно, чтобы не разругивать последний шаг, всё выражение берется в скобки и последняя скобка выталкивает все оставшиеся операции.
Q = {4} и W={}

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

Пример: 2 + 1 – 6 / (1 + 2)
Рассмотрим пример по шагам:


Q.push(2)

Q = {2}

W = { }
W.push(+)

Q = {2}

W = {+}
Q.push(1)

Q = {2, 1}

W = {+}
W.push(-)

у операций + и – приоритет равный, следовательно выталкиваем + 

Q = {3}

W = {-}
Q.push(6)

Q = {3, 6}

W = {-}
W.push( / )

Q = {3, 6}

W = {-, /}
W.push( ( )

открывающаяся скобка никого не выталкивает, а просто добавляет себя в стек операций

Q = {3, 6}

W = {-, /, (}
Q.push(1)

Q = {3, 6, 1}

W = {-, /, (}
W.push(+)

открывающуюся скобку может вытолкнуть только закрывающаяся. ничего не делаем.

Q = {3, 6, 1}

W = {-, /, (, +}
Q.push(2)

Q = {3, 6, 1, 2}

W = {-, /, (, +}
W.push( ) )

Закрывающаяся скобка выталкивает все операции до первой открывающейся

такая операция почти всегда одна (зависит от реализации)

Q = {3, 6, 3}

W = {-, /}
Вот на этом шаге мы или сами разруливаем концовку или изначально оборачиваем выражение в круглые скобки, чтобы вытолкнуть все оставшиеся операции

Q = {3, 2, 3}

W = {-, /}
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