Verify Mathematical Equation c++

Question

I am currently trying to build a very simple compiler. I have created a function that converts a mathematical equation in infix notation to RPN using the shunting-yard algorithm however I have encountered a problem. I did not include error checking in my conversion function so I was wondering if there was a simple way to check if a function in infix notation is in correct infix notation syntax. This would enable me to keep my current conversion function without obscuring it with error checking.

Answer 1

If your expressions only consist of parentheses, values (constants and/or identifiers), and prefix, postfix and infix operators, then there are two error conditions you need to check:

1. The parentheses must match. It's hard not to notice this with the shunting yard algorithm, because there is a point in the algorithm where an open parenthesis is popped off the stack when a close parenthesis is encountered in the input. If you overpop the stack or you don't pop the entire stack at end of input, then the parentheses didn't balance.

2. The tokens must conform to the following simple regular expression:

   PRE* VAL POST* ( INFIX PRE* VAL POST* )*
   

   where

   • PRE is a prefix operator or an (
   • POST is a postfix operator or a )
   • VAL is a value: a constant or an identifier

That actually reduces to a two-state state machine: the initial state (state 0) could be called "expecting value" and the other state (state 1) could be called "expecting operator". Only state 1 is accepting, and the transitions are as follows:

State 0:
    PRE   → State 0
    VAL   → State 1

State 1:
    POST  → State 1
    INFIX → State 0

All other transitions are to an error.

It's often necessary to implement this state machine in order to properly deal with unary minus (and other operators which could be prefix or infix), and it is, in any event, very simple to integrate into your input handling.