Как стать автором
Обновить

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

Алгоритмы *
В продолжение поста Компилятор выражений. По просьбам читающих. Специально для 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}

Если пост понравился, в следующем напишу о том, как я делал небольшой функциональный язык и объектно-ориентированный язык.
Теги:
Хабы:
Всего голосов 59: ↑55 и ↓4 +51
Просмотры 46K
Комментарии 36
Комментарии Комментарии 36

Публикации

Истории