1

I'm interested in all the cases where shunting-yard algorithm can tell if an expression is not correctly written from a syntax point of view.

So the Shunting-yard algorithm takes an expression written in infix notation and transforms it into prefix or postfix notation. As a simple example, the one taken from wikipedia: an infix notation of an equation would be 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3 and after being converted to postfix with the algorithm it would become 3 4 2 × 1 5 − 2 3 ^ ^ ÷ +.

The algorithm on wikipedia checks for mismatched parentheses in two cases: First, if it finds a right bracket then pops the operators till a left bracket is found, if it's not found then there are mismatched parentheses. Second, after all tokens are read it pops the operator stack into output queue. If there is a bracket left, there are mismatched parentheses. These 2 things can be done with the algorithm.

Now for my expression in postfix notation 3 4 2 × 1 5 − 2 3 ^ ^ ÷ + how exactly can I say from this that my infix notation was correctly written? I've been thinking that after this expression is evaluated if there is more than one element in the stack then there is an error. What are some other cases I should consider?

  • Well obviously if you execute a postfix notation expression and end up with a operand or operator extra, something went wrong. That aside, it isn't necessarily true that the ordering of the operations is honored. A possible way of checking would be to evaluate a infix expression evaluator and a postfix expression evaluator and compare the results of both, but that doesn't guarantee the algorithm works as they could be the same by chance, such as evaluting (2 + 2) + 2 vs 2 + (2 + 2). – Neil Oct 30 '18 at 9:47
2

Postfix notation is easy to statically check, provided that you can easily look up the arity of operators. You can iterate through all elements and can keep track of the number of elements on the evaluation stack. This size must always be at least one. At the end, the size must be exactly one. Pseudocode for verification:

operations = [...]
size = 0

for operand in operations:
  switch operand type:
    case literal:
      size = size + 1
    case operator:
      assert size >= arity(operand)
      size = size + 1 - arity(operand)

assert size == 1

However, for a simple calculator language there is no benefit of performing static analysis over simply executing the code and see whether it leads to an inconsistent state.

1

One additional issue when parsing infix is when you have 2 numbers or 2 operators next to each other: 2 2 + + 3

You check for this by only accepting a number or left parentheses after a operator or left parentheses and only accept a operator or right parentheses after a number or right parentheses.

if(expectOperator){
    if(token.type == NUMBER || token.type == LEFT_PAREN){
        error("expect operator");
    } 
} else{
    if(token.type == OPERATOR || token.type == RIGHT_PAREN){
        error("expect number");
    } 
}
if(token.type != RIGHT_PAREN && token.type != LEFT_PAREN)
    expectOperator =! expectOperator;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.