Transfer yard Algorithm: Novel mathematical infix to postfix expression evaluator with minimum stack operations

Abstract

Reverse Polish Notation (RPN) is vital in evaluating machines' mathematical expressions. Further, it has many important applications. For more than 50 years, RPN Shunting Yard was utilized to evaluate mathematical expressions written infix notation. Most resources recommend using the Shunting yard algorithm to convert infix to RPN notation. In this paper, we proposed a variant shunting yard algorithm named Transfer Yard algorithm (TY) that transfers infix expression to RPN. The proposed algorithm has the advantage of using an array structure with minimum stack operations. The array structure is proved to have better performance in compassion of utilizing stack memory. Actually, utilizing array structure benefits of random access. In the proposed algorithm, we utilized the array to arrange operators' precedency so we can perform transformation in an efficient way. We implemented the proposed algorithm and compared its performance with the Shunting Yard algorithm. To achieve a highly accurate comparison, we designed experiments that minimize any artifact that would affect the results. For that purpose, we repeated the experiment in the same environment more than thousand time and selected the lowest time to represent the execution time for those inputs. Furthermore, both algorithms are tested with variable inputs. Results show that the proposed transfer yard algorithm's performance is significantly better than the performance of the Shunting Yard algorithm.