\Section{Арифметические выражения}{25 сентября}{Даниил Смирнов}
\Subsection{Без стека +, -, *, /, (, )}
  \begin{enumerate}[a.]
    \item Найдем последнюю операцию \\
    По скобкам храним балансы на префиксах. Тогда порядок выполнения операций такой: 
    Максимальный баланс, максимальный приоритет, самая левая из возможных (так как все 
    левоассоциативны)
    \item 2 рекурсивных вызова - посчитаем правый и левый аргумент и применим операцию к ним
    Время: $\O(n^2)$ в худшем случае
    \item Случай: операции внутри скобок кончились $\rightarrow$ уберем их
  \end{enumerate}

\Subsection{Со стеком} \\
  \Subsubsection{Без скобок} \\
    Если приходит число, отправим его в стек чисел, операция --- в стек операций. Пока
    у пришедшей операции приоритет не больше, чем у последней, выполняем последнюю для 
    двух последних чисел, заменяя их на результат.
    \begin{lstlisting}[gobble=6]
      while (prior(oper.top()) >= prior(new)) {
        eval();
      }
      oper.push(new);
    \end{lstlisting}
    Еще может случиться, что у нас есть правоассоциативные операции. Тогда условие
    заменяется на:
    \begin{lstlisting}[gobble=6]
      (prior(top()) > prior(new) || (prior(top()) == prior(new) && type[new] == "L"))
    \end{lstlisting}
  \Subsubsection{Со скобками}
    \begin{lstlisting}[gobble=6]
      // prior["("] = +inf;
      // prior[")"] = 0;
      while (top() != "(" && prior(top()) >= prior(new))
        eval();
      if (new == ")")
        oper.pop();
      else
        oper.push(new);
    \end{lstlisting}
  \Subsubsection{Унарный минус}
    \begin{enumerate}[a.]
      \item $2-\sim3$
        \begin{lstlisting}[gobble=10]
          while (unary(open.top()))
            x = eval(x);
          values.push(x)
        \end{lstlisting}
      \item $1\-\-\-2 = 1-(-(-2))$
        Если последний push в стек операций, то наш минус --- унарный, иначе бинарный
    \end{enumerate}
\Subsection{Дерево выражений} \\
  Пусть у нас есть переменные. Тогда будем в стеке чисел хранить указатели на вершины дерева выражений. Можно будет подставить значения и посчитать ответ.
  \begin{lstlisting}[gobble=4]
    Node {
      int type;
      int value;
      Node *a, *b;
    }
  \end{lstlisting}