Имейте в виду алгоритм Shunting-yard, нужно помочь ему разобраться

Question

Я пытаюсь реализовать алгоритм Shunting-yard без круглых скобок, но мне трудно понять его. Я пробовал википедию, но запись действительно плохая. У меня должно быть мало проблем с реализацией кода, но если я не получу, я не смогу его реализовать.

Теперь: как работает этот алгоритм?

Вот что я понимаю:

• Go слева направо, все числа добавляются в выходной очереди, все операнды добавляются в стек. После того, как вы дойдете до конца вы поп все операнды и добавить их к выходу

  Expression: 2+5*4+3/5 (= 2+20+0.6 = 22.6) 
  
  Stack: +*+/    (-> top) 
  
  OutputQueue: 5 3 4 5 2 (-> exits) 
  

Теперь я вытолкнуть стек и добавить его в очередь

OutputQueue: (insert ->) + * +/5 3 4 5 2 (-> exit) 

Так, насколько я понимаю, форма должна быть: 25435/+ * +

Давайте попробуем решить:

5/3 ~ 1.6 + 4 ~= 5.6 * 5 ~= 28 + 2 ~= 30 (or 30.3 recurring .3 if you insist) 

EDIT: Я уверен, что Reverse Polish notation Я использовал здесь правильно, так что это не должно быть проблемой.

Я знаю, что я делаю что-то глупое, но для жизни меня не могу понять.

Я думаю, что это поможет большинству, если кто-то может указать на ошибку в моей логике, потому что алгоритм должен быть хорошим, так как он из википедии, и я видел, как другие указывают мне на это. Так что это должно быть хорошо, я просто что-то испортил.

Является ли это очередью? Я уверен, что достаточно хорошо разбираюсь в Reverse Polish notation.

Answer 1

Вы получили это неправильно:

Expression: 2+5*4+3/5 

Для каждого маркера:

token : 2 
    outputqueue 2 
    stack 

    token : + 
    outputqueue 2 
    stack + 

    token : 5 
    outputqueue 25 
    stack + 

    token : "*" 
    "*" has higher predencence as "+", so we push into the stack 
    outputqueue 25 
    stack +* 

    token : 4 
    outputqueue 254 
    stack +* 

    token : "+" 
    "+ "has lower predencence as "*", we pop "*" from the stack. 
    "+" has same predecence as "+", so we pop "+" from the stack then add the current token "+" in the stack 
    outputqueue 254*+ 
    stack + 

    token : 3 
    outputqueue 254*+3 
    stack + 

    token : "/" 
    "/" has lower predencence as "+", we push "/" into the stack 
    outputqueue 254*+ 
    stack +/ 

    token : 5 
    outputqueue 254*+35 
    stack +/ 

Выражение закончится, выскочит стек:

output 254*+35/+ 

---

Расчет:

5*4 = 20 
2+20 = 22 
3/5 = 0.6 
22 + 0.6 = 22.6 

Answer 2

Я не уверен, что алгоритм, который вы хотите, достаточно прост - прочитал ли вы всю статью о вики, на которую вы ссылаетесь? В частности, в разделе «The algorithm in detail» много говорится о приоритете оператора, который, я думаю, вы отбрасываете в своей текущей реализации. Мое предложение состоит в том, чтобы пройти через этот раздел по одному шагу за шагом, следуя пунктам (и по сравнению с приведенным ниже примером по мере необходимости), чтобы попытаться найти подходящую форму для этой проблемы. Как только вы это сделаете, он, надеюсь, поможет вам понять алгоритм в целом.