la difficulté à comprendre ce qu'il faut faire avec la sortie de l'algorithme shuntage-cour
-
27-10-2019 - |
Question
J'ai regardé à la page wiki: http://en.wikipedia.org/ wiki / Manœuvres-yard_algorithm
Je l'ai utilisé l'exemple de code pour construire la première partie, au fond, je peux actuellement tourner:
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
dans 3 4 2 * 1 5 − 2 3 ^ ^ / +
Mais je ne sais pas comment utiliser ensuite 3 4 2 * 1 5 − 2 3 ^ ^ / +
pour obtenir 3.00012207
Et l'exemple de code et une explication sur le wiki ne sont pas me aucun sens.
Quelqu'un pourrait-il s'il vous plaît expliquer comment évaluer 3 4 2 * 1 5 − 2 3 ^ ^ / +
et produire la réponse. Merci d'avance. Je ne suis pas besoin d'un exemple de code juste une bonne explication ou d'une panne d'un exemple.
Non que cela importe, mais je travaille .net C #.
La solution
The purpose of the shunting yard algorithm is that its output is in Reverse Polish Notation, which is straightforward to evaluate:
- create a stack to hold values
- while there is reverse polish notation input left:
- read an item of input
- if it is a value, push it onto the stack
- otherwise, it is an operation; pop values from the stack, perform the operation on those values, push the result back
- when there's no input left, if the expression was well formed, there should be exactly one value on the stack; this is the evaluated result.
Autres conseils
The post-fix notation is how you do the math in, say, a HP calculator.
Keep a stack, whenever you get a number add it to the top. Whenever you get an operator consume inputs from the top and then add the result to the top
token stack
*empty*
3 3 //push numbers...
4 3 4
2 3 4 2
* 3 8 //remove 4 and 2, add 4*2=8
1 3 8 1
5 3 8 1 5
- 3 8 -4
2 3 8 -4 2
3 3 8 -4 2 3
^ 3 8 -4 8
... ...
Process the elements 3 4 2 * 1 5 − 2 3 ^ ^ / +
left-to-right as follows:
- Initialize a stack to hold numbers.
- If the element is a number, push it onto the stack.
- if the element is an operator, remove the top two elements from the stack, apply the operator to those two elements, and push the result onto the stack.
When you get to the end, the stack should have a single element which will be the result.
I see I am a bit late to the party.
I saw the question and went off on a tangent writing a couple of tasks for Rosetta Code. It just so happens that this task might be what you are after. It gives an annottated table of what happens when calculating the value of an RPN expression, token by token.
Here is a sample of its output:
For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +'
TOKEN ACTION STACK
3 Push num onto top of stack 3
4 Push num onto top of stack 3 4
2 Push num onto top of stack 3 4 2
* Apply op to top of stack 3 8
1 Push num onto top of stack 3 8 1
5 Push num onto top of stack 3 8 1 5
- Apply op to top of stack 3 8 -4
2 Push num onto top of stack 3 8 -4 2
3 Push num onto top of stack 3 8 -4 2 3
^ Apply op to top of stack 3 8 -4 8
^ Apply op to top of stack 3 8 65536
/ Apply op to top of stack 3 0.0001220703125
+ Apply op to top of stack 3.0001220703125
The final output value is: '3.0001220703125'