Проблема распараллеливания выражений является наиболее изученной в параллельном программировании. Формально выражение – это ациклический процесс и к нему можно подходить так же, как в предыдущем параграфе. Однако здесь есть и принципиальное отличие – в выражениях не всегда указан порядок действий. Например, следующие выражения эквиваленты (с математической точки зрения):

Задача распараллеливания выражений ставится следующим образом: построить алгоритм, который каждому выражению ставит в соответствие эквивалентное ему с минимальной высотой ЯПФ. Здесь эквивалентность понимается в смысле применения обычных законов ассоциативности , коммутативности и дистрибутивности .
Заметим, что применение закона дистрибутивности при эквивалентных преобразованиях требует большой осторожности, поскольку при этом возможно, например, переполнение. Например, если в выражении величины , – большие положительные числа, то умножение может быть выполнено без осложнений, но умножения в эквивалентном выражении могут вызвать переполнение.
Покажем на примере как может меняться высота ЯПФ при изменении порядка действий в выражении.
Пример 1
Рассмотрим выражение
 (1)

ЯПФ выражения (1) приведена на рис. 1.
Рис. 1.  ЯПФ выражения (1)
Перепишем выражение (1) в эквивалентном виде
 (2)

ЯПФ, соответствующая этому выражению, приведена на рис. 2
Рис. 2.  ЯПФ выражения (2)
Доказано, что любое арифметическое выражение без унарного минуса с операторами может быть вычислено на /2 процессорах за время порядка при сложности преобразования в максимально-параллельную форму .