Editing Shunting yard algorithm
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 34: | Line 34: | ||
==Extensions== | ==Extensions== | ||
===Unary operators=== | ===Unary operators=== | ||
− | Unary minus signs (and possibly unary plus signs) often appear in infix expressions. There are | + | Unary minus signs (and possibly unary plus signs) often appear in infix expressions. There are two modifications that have to be made to the algorithm in order to handle these: |
* A minus sign is always binary if it immediately follows an operand or a right parenthesis, and it is always unary if it immediately follows another operator or a left parenthesis, or if it occurs at the very beginning of the input. The algorithm must be modified in order to distinguish between the two. | * A minus sign is always binary if it immediately follows an operand or a right parenthesis, and it is always unary if it immediately follows another operator or a left parenthesis, or if it occurs at the very beginning of the input. The algorithm must be modified in order to distinguish between the two. | ||
− | |||
* Unary minus signs and binary minus signs must be distinguished in the output in order to avoid ambiguity. Because postfix expressions are intended to be evaluated from left to right, we have a problem with an expression like <code>1 2 - 3 +</code> if the minus sign is allowed to be unary; upon reaching it, we cannot determine whether it is unary or binary. If it is binary, then both of the preceding operands belong to it, and if it is unary, then only one of the two belongs to it, but perhaps the other belongs to some following operator. It is advisable to have some separate symbol for unary and binary minus signs, as is common in handheld scientific calculators. Also, this symbolic distinction must be made before the operator is pushed onto the stack, because once it is on the stack, we lose the ability to retrospectively determine whether it was supposed to be unary or binary. | * Unary minus signs and binary minus signs must be distinguished in the output in order to avoid ambiguity. Because postfix expressions are intended to be evaluated from left to right, we have a problem with an expression like <code>1 2 - 3 +</code> if the minus sign is allowed to be unary; upon reaching it, we cannot determine whether it is unary or binary. If it is binary, then both of the preceding operands belong to it, and if it is unary, then only one of the two belongs to it, but perhaps the other belongs to some following operator. It is advisable to have some separate symbol for unary and binary minus signs, as is common in handheld scientific calculators. Also, this symbolic distinction must be made before the operator is pushed onto the stack, because once it is on the stack, we lose the ability to retrospectively determine whether it was supposed to be unary or binary. | ||
It should also be pointed out that the unary minus sign is usually treated as though it has higher precedence than <code>*</code> and <code>/</code>. For example, the expression <code>10/-1*-2</code> usually evaluates to 20 rather than 5. | It should also be pointed out that the unary minus sign is usually treated as though it has higher precedence than <code>*</code> and <code>/</code>. For example, the expression <code>10/-1*-2</code> usually evaluates to 20 rather than 5. |