Giter Club home page Giter Club logo

shuntingyard's Introduction

About this project

Different programming languages provide different capabilities.
The same application, a console term calculator, using the same technique (i.e. the shunting yard algorithm to transform infix notation into postfix notation), is implemented in different languages here; these are

Although the underlying algorithmic principle is always the same, this approach tries to take advantage of the particular properties of each language, namely

  • C has a small set of commands, provides direct access to memory addresses and can therefore be very fast.
  • C++ has (more or less) the same features as C, but simplifies the developer's work, especially in questions related to memory management.
  • Java To cite a friend: From the perspective of Java, the developer is a virus from whom the code must be protected. - Consider it funny
  • Javascript is a completely dynamic language, having functions being so-called First Class Citizens.
  • PHP is a typeless language (there is at least no general distinction between numbers and strings) with an emphasis on collection based operations.
  • Ruby is an Object Oriented Language. This is much more than A language supporting Object Oriented Programming; in Ruby, so-called primitive types, the values of primitive types or even classes are objects. As a result, the Ruby application's code is the shortest in this collection.
  • Swift, even though the youngest in this formation, is quite conservative and extremely typesafe.

 

Reverse Polish Notation

In (elementary) arithmetics, operators are usually written between numbers; when an operator is found, the execution command is

Do something with number left of operator and number right of operator

If the term contains more than one operator, it is ambiguous:

2 + 3 * 4

will lead to different results, depending on whether 2 + 3 or 3 * 4 is calculated first.

Following common convention, * and / are preferred over + and -, but this (as well as any other imaginable rule) does not cover the cases if a different behaviour is wanted. The problem is solved by setting brackets: Brackets always have higher precedence than operators.

In the 1920s, Jan Łukasiewicz invented a notation where operators precede their numbers (more generally: their operands), known as Prefix Notation or Polish Notation; for practical reasons, this is often used in reverse order such that operators follow their operands, known as Postfix Notation or Reverse Polish Notation.

Without any usage of brackets, the execution rule always is unambiguous:

Do something with number two positions left of operator and number one position left of operator

Extended to a complete algorithm for term execution, this is

While term still has more than one element
    Replace most left operator with result of calculation [position - 2] [operator] [position - 1]
    Delete both used numbers
Result is remaining number

The above example would be written as

2 3 4 * +

A more complex example would be

((1 - (2 - (3 - (4 - (5 - 6))))) - 7 * (7 - (6 - (5 - (4 - (3 - 2))))) + 1) * -1

what in Postfix Notation is written as

1 2 3 4 5 6 - - - - - 7 7 6 5 4 3 2 - - - - - * - 1 + -1 *

Considerations about the usefulness of Reverse Polish Notation obviously lead to the question

Is it possible to rewrite any possible vaild term in Reverse Polish Notation?

The answer can be found either in giving mathematical proof either in providing an algorithm which transforms traditional (infix) notation into postfix notation; if this algorithm can deal with any given term, the above question is answered.

Edsger W. Dijkstra invented such an algorithm and called it Shunting Yard. Since Dijkstra was not only programmer but also mathematician and logician, the method's practical purpose is not self-evident.

The costs for executing a term written in infix notation directly are obviously not only proportional to the amount of elements but also proportional to the amount of bracket pairs; the overall costs will grow exponentially for longer terms.

A term written in postfix notation has, due to the absence of bracket, linearly growing costs. The Shunting Yard Algorithm itself also has linearly growing costs. Therefore, for longer terms (where the base costs do not have to be taken into consideration), execution will benefit of transforming traditionally written terms into Reverse Polish Notation.

shuntingyard's People

Contributors

mentalmove avatar

Stargazers

 avatar

Watchers

 avatar

Forkers

el17wl

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.