Вот это алгоритм из Википедии:

Но я не могу понять, что такое символ функции и оператор o1. Я сначала думал, что символ функции — это просто оператор. Но тогда чем от обычных операторов отличается o1? Объясните, пожалуйста.

sidd, 
exp это три символа. exp, not, rand это функции. Для применения автомата введем новый набор символов. Где каждую функцию обозначим своим символом.  К примеру exp-"e", not-"n",rand- "r"
Весь наш алфавит состоит из "0","1","2","3","4","5","6","7","8","9","+","-","*","e","n","r".  Зачем это нужно? Да просто по тому что магазинный автомат работает с алфавитом. Так проще понимать. Даже более того все числа которые есть в строке по хорошему надо представить как некоторый символ.

Вопрос чем функция отличается от оператора? Функция всегда имеет наивысший приоритет и является право ассоциативной.

Тогда она всегда помещается в стек.  Так как нет наиболее высшего оператора. Другими словами для функции условие 

никогда не выполняется.


Остается самое главное отличие функции от оператора. После функции всегда идут скобки.


Почему оператор тут называется O1 ? Трудно сказать просто это списано из какой то книжке. Скорее всего индекс 1 . Взялся из грамматике. Все операторы у нас имеют по 1 символу поэтому в рассмотрении и участвует один символ O1 где 1 индекс. 


Советую википедию не читать, а читать умные книжки.
Вот тут не плохо описано.
 http://www.intuit.ru/department/sa/compilersdev/


1)Начни с Формальной грамматики. 
2)Дальше перейди к конечным автоматом.  
3)После автомат с магазинной памятью.

Тут собственно и будет обратная польская нотация. Советую о функциях забыть и рассматривать польскую нотацию как метод избавления от скобок.  Грамматика очень проста.
E="("E")"|число
E=E"+"E |E"-"E|E"*"E| E"/"E

Основное что тут надо уловить это приоритет операций и построение по грамматике автомата. 
Понять почему запись выше может интерпретироваться по разному. И как от этого избавится. Доказать возможность построение автомата с магазинной память.

Основной подход для построения автомата это рассмотреть все множество состояний в этом языке. Для этого существует множество подходов LL и RL. Но тут для наглядности лучше ручками разобрать. Понять что возможных состояний автомата может быть много и очень много. Тут не плохо бы знать динамическое программирование.  Оно поможет легко и просто построить автомат.

Спасибо, теперь уже разобрался. Ну автомат я не строил, так как это просто лаба обычная, там и так сойдет. А вообще интересно очень. Зря я, наверно, на дискретку на первом курсе забивал.