State 0: Increment index string index If current input is number, next state is 1 If current input is operator, next state is 2 If current input is left parenthesis, next state is 3 If current input is right parenthesis, next state is 4 If current input is end of string, next state is 5 If current input is garbage, next state is 6 State 1: (found number) Copy current character to output string Increment output string index Increment input string index While character in input string is digit or decimal point o Copy character to output string o Increment output string index o Increment input string index Put space in output string Increment output string index Decrement input string index Next state is 0 State 2: (found operator) While the stack is not empty and the character at top of stack is an operator and the precedence of the operator that is current character in input string is less than or equal to that of the operator on top of the stack o Pop operator off top of stack and put in output string o Increment output string index o Put space in output string o Increment output string index If stack is not full, Push the operator that is current character in input string on stack Otherwise, print error and exit Next state is 0 State 3: (found left parenthesis) If stack is not full, push left parenthesis found in current input character on stack Otherwise, display error message and exit Next state is 0 State 4: (found right parenthesis) While stack is not empty and item at top of stack is not left parenthesis o Pop operator off top of stack and put in output string o Increment output string index o Put space in output string o Increment output string index If stack is not empty, pop left parenthesis off stop of stack but do not put in output string Otherwise, display error message (mismatched parenthesis) and exit Next state is 0 State 5: (End of input) While stack is not empty and character at top of stack is an operator o Pop operator off stack and put in output string o Increment output string index o Put space in output string o Increment output string index If stack is not empty, display error message (leftover parenthesis) and exit Otherwise, put end of string marker in output string and send output string to RPN Evaluator Note: return rpneval(output_string); State 6: (garbage) Display error message and exit