Hands-On Data Structures and Algorithms with JavaScript

To install the Angular CLI in your Terminal, run the following command:

npm install -g @angular/cli

That should install the Angular CLI globally and give you access to the ng command to create new projects.

To test it, you can run the following command, which should show you a list of features available for use:

ng

Now, let's create the Angular application. We will create a new application for each example for the sake of clarity. You can club them into the same application if you feel comfortable. To create an Angular application using the CLI, run the following command in the Terminal:

ng new <project-name>

Replace project-name with the name of your project; if everything goes well, you should see something similar on your Terminal:

 installing ng
 create .editorconfig
 create README.md
 create src/app/app.component.css
 create src/app/app.component.html
 create src/app/app.component.spec.ts
 create src/app/app.component.ts
 create src/app/app.module.ts
 create src/assets/.gitkeep
 create src/environments/environment.prod.ts
 create src/environments/environment.ts
 create src/favicon.ico
 create src/index.html
 create src/main.ts
 create src/polyfills.ts
 create src/styles.css
 create src/test.ts
 create src/tsconfig.app.json
 create src/tsconfig.spec.json
 create src/typings.d.ts
 create .angular-cli.json
 create e2e/app.e2e-spec.ts
 create e2e/app.po.ts
 create e2e/tsconfig.e2e.json
 create .gitignore
 create karma.conf.js
 create package.json
 create protractor.conf.js
 create tsconfig.json
 create tslint.json
 Installing packages for tooling via npm.
 Installed packages for tooling via npm.
 Project 'project-name' successfully created.

If you run into any issues, ensure that you have angular-cli installed as described earlier. 

Before we write any code for this application, let's import the stack that we earlier created into the project. Since this is a helper component, I would like to group it along with other helper methods under the utils directory in the root of the application.

Since the code for an Angular application is now in TypeScript, we can further optimize the stack that we created. Using TypeScript makes the code more readable thanks to the private variables that can be created in a TypeScript class.

So, our TypeScript-optimized code would look something like the following:

export class Stack {
    private wmkey = {};
    private items = new WeakMap();

    constructor() {
        this.items.set(this.wmkey, []);
    }

    push(element) {
        let stack = this.items.get(this.wmkey);
        stack.push(element);
    }

    pop() {
        let stack = this.items.get(this.wmkey);
        return stack.pop();
    }

    peek() {
        let stack = this.items.get(this.wmkey);
        return stack[stack.length - 1];
    }

    clear() {
        this.items.set(this.wmkey, []);
    }

    size() {
        return this.items.get(this.wmkey).length;
    }
}

To use the Stack created previously, you can simply import the stack into any component and then use it. You can see in the following screenshot that as we made the WeakMap() and the key private members of the Stack class, they are no longer accessible from outside the class:

>

Public methods accessible from the Stack class

Now that we have the base code set up, let's list the steps for us to build an app that will enable us to create a custom Back button in a browser:

Let's quickly add a few states to the application, which are also known as routes in Angular. All SPA frameworks have some form of routing module, which you can use to set up a few routes for your application.

Once we have the routes and the routing set up, we will end up with a directory structure, as follows:

Directory structure after adding routes

Now let's set up the navigation in such a way that we can switch between the routes. To set up routing in an Angular application, you will need to create the component to which you want to route and the declaration of that particular route. So, for instance, your home.component.ts would look as follows:

import { Component } from '@angular/core';

@Component({
    selector: 'home',
    template: 'home page'
})
export class HomeComponent {

}

The home.routing.ts file would be as follows:

import { HomeComponent } from './home.component';

export const HomeRoutes = [
    { path: 'home', component: HomeComponent },
];

export const HomeComponents = [
    HomeComponent
];

We can set up a similar configuration for as many routes as needed, and once it's set up, we will create an app-level file for application routing and inject all the routes and the navigatableComponents in that file so that we don't have to touch our main module over and over.

So, your file app.routing.ts would look like the following:

import { Routes } from '@angular/router';
import {AboutComponents, AboutRoutes} from "./pages/about/about.routing";
import {DashboardComponents, DashboardRoutes} from "./pages/dashboard/dashboard.routing";
import {HomeComponents, HomeRoutes} from "./pages/home/home.routing";
import {ProfileComponents, ProfileRoutes} from "./pages/profile/profile.routing";

export const routes: Routes = [
    {
        path: '',
        redirectTo: '/home',
        pathMatch: 'full'
    },
    ...AboutRoutes,
    ...DashboardRoutes,
    ...HomeRoutes,
    ...ProfileRoutes
];

export const navigatableComponents = [
    ...AboutComponents,
    ...DashboardComponents,
    ...HomeComponents,
    ...ProfileComponents
];

You will note that we are doing something particularly interesting here:

{
    path: '',
    redirectTo: '/home',
    pathMatch: 'full'
}

This is Angular's way of setting default route redirects, so that, when the app loads, it's taken directly to the /home path, and we no longer have to set up the redirects manually.

To detect a state change, we can, luckily, use the Angular router's change event and take actions based on that. So, import the Router module in your app.component.ts  and then use that to detect any state change:

import { Router, NavigationEnd } from '@angular/router';
import { Stack } from './utils/stack';

...
...

constructor(private stack: Stack, private router: Router) {

    // subscribe to the routers event
    this.router.events.subscribe((val) => {

        // determine of router is telling us that it has ended
        transition
        if(val instanceof NavigationEnd) {

            // state change done, add to stack
            this.stack.push(val);
        }
    });
}

Any action that the user takes that results in a state change is now being saved into our stack, and we can move on to designing our layout and the back button that transitions the states.

We will use angular-material to style the app, as it is quick and reliable. To install angular-material, run the following command:

npm install --save @angular/material @angular/animations @angular/cdk

Once angular-material is saved into the application, we can use the Button component provided to create the UI necessary, which will be fairly straightforward. First, import the MatButtonModule that we want to use for this view and then inject the module as the dependency in your main AppModule.

The final form of app.module.ts would be as follows:

import { BrowserModule } from '@angular/platform-browser';
import { NgModule } from '@angular/core';
import { FormsModule } from '@angular/forms';
import { HttpModule } from '@angular/http';
import { BrowserAnimationsModule } from '@angular/platform-browser/animations';
import { MatButtonModule } from '@angular/material';

import { AppComponent } from './app.component';
import { RouterModule } from "@angular/router";
import { routes, navigatableComponents } from "./app.routing";
import { Stack } from "./utils/stack";

// main angular module
@NgModule({
    declarations: [
        AppComponent,

        // our components are imported here in the main module
        ...navigatableComponents
    ],
    imports: [
        BrowserModule,
        FormsModule,
        HttpModule,

        // our routes are used here
        RouterModule.forRoot(routes),
        BrowserAnimationsModule,

        // material module
        MatButtonModule
    ],
    providers: [
        Stack
    ],
    bootstrap: [AppComponent]
})
export class AppModule { }

We will place four buttons at the top to switch between the four states that we have created and then display these states in the router-outlet directive provided by Angular followed by the back button. After all this is done, we will get the following result:

<nav>
    <button mat-button 
        routerLink="/about" 
        routerLinkActive="active">
      About
    </button>
    <button mat-button 
        routerLink="/dashboard" 
        routerLinkActive="active">
      Dashboard
    </button>
    <button mat-button 
        routerLink="/home" 
        routerLinkActive="active">
      Home
    </button>
    <button mat-button 
        routerLink="/profile"
        routerLinkActive="active">
      Profile
    </button>
</nav>

<router-outlet></router-outlet>

<footer>
    <button mat-fab (click)="goBack()" >Back</button>
</footer>

To add logic to the back button from here on is relatively simpler. When the user clicks on the Back button, we will navigate to the previous state of the application from the stack. If the stack was empty when the user clicks the Back button, meaning that the user is at the starting state, then we set it back into the stack because we do the pop() operation to determine the current state of the stack.

goBack() {
    let current = this.stack.pop();
    let prev = this.stack.peek();

    if (prev) {
        this.stack.pop();

        // angular provides nice little method to 
        // transition between the states using just the url if needed.
        this.router.navigateByUrl(prev.urlAfterRedirects);

    } else {
        this.stack.push(current);
    }
}

Note here that we are using urlAfterRedirects instead of plain url. This is because we do not care about all the hops a particular URL made before reaching its final form, so we can skip all the redirected paths that it encountered earlier and send the user directly to the final URL after the redirects. All we need is the final state to which we need to navigate our user because that's where they were before navigating to the current state.

So, now our application is ready to go. We have added the logic to stack the states that are being navigated to and we also have the logic for when the user hits the Back button. When we put all this logic together in our app.component.ts, we have the following:

import {Component, ViewEncapsulation} from '@angular/core';
import {Router, NavigationEnd} from '@angular/router';
import {Stack} from "./utils/stack";

@Component({
    selector: 'app-root',
    templateUrl: './app.component.html',
    styleUrls: ['./app.component.scss', './theme.scss'],
    encapsulation: ViewEncapsulation.None
})
export class AppComponent {
    constructor(private stack: Stack, private router: Router) {
        this.router.events.subscribe((val) => {
            if(val instanceof NavigationEnd) {
                this.stack.push(val);
            }
        });
    }

    goBack() {
        let current = this.stack.pop();
        let prev = this.stack.peek();

        if (prev) {
            this.stack.pop();
            this.router.navigateByUrl(prev.urlAfterRedirects);
        } else {
            this.stack.push(current);
        }
    }
}

We also have some supplementary stylesheets used in the application. These are obvious based on your application and the overall branding of your product; in this case, we are going with something very simple.

For the AppComponent styling, we can add component-specific styles in app.component.scss:

.active {
  color: red !important;
}

For the overall theme of the application, we add styles to the theme.scss file:

@import '~@angular/material/theming';
// Plus imports for other components in your app.

// Include the common styles for Angular Material. We include this here so that you only
// have to load a single css file for Angular Material in your app.
// Be sure that you only ever include this mixin once!
@include mat-core();

// Define the palettes for your theme using the Material Design palettes available in palette.scss
// (imported above). For each palette, you can optionally specify a default, lighter, and darker
// hue.
$candy-app-primary: mat-palette($mat-indigo);
$candy-app-accent:  mat-palette($mat-pink, A200, A100, A400);

// The warn palette is optional (defaults to red).
$candy-app-warn:    mat-palette($mat-red);

// Create the theme object (a Sass map containing all of the palettes).
$candy-app-theme: mat-light-theme($candy-app-primary, $candy-app-accent, $candy-app-warn);

// Include theme styles for core and each component used in your app.
// Alternatively, you can import and @include the theme mixins for each component
// that you are using.
@include angular-material-theme($candy-app-theme);

This preceding theme file is taken from the Angular material design documentation and can be changed as per your application's color scheme.

Once we are ready with all our changes, we can run our application by running the following command from the root folder of our application:

ng serve

That should spin up the application, which can be accessed at http://localhost:4200.

From the preceding screenshot, we can see that the application is up-and-running, and we can navigate between the different states using the Back button we just created.

Once we have the app created and instantiated, we will create the worker.js file first using the following commands from the root of your app:

cd src/app
mkdir utils
touch worker.js

This will generate the utils folder and the worker.js file in it.

Note the following two things here:

Web workers are used to simulate the concept of multithreading in JavaScript, which is usually not the case. Also, since this thread runs in isolation, there is no way for us to provide dependencies to that. This works out very well for us because our main app is only going to accept the user's input and provide it to the worker on every key stroke while it's the responsibility of the worker to evaluate this expression and return the result or the error if necessary.

Since this is an external file and not a standard Angular file, we will have to load it up as an external script so that our application can use it subsequently. To do so, open your .angular-cli.json file and update the scripts option to look as follows:

...
"scripts": [
  "app/utils/worker.js"
],
...

Now, we will be able to use the injected worker, as follows:

this.worker = new Worker('scripts.bundle.js');

First, we will add the necessary changes to the app.component.ts file so that it can interact with worker.js as needed. 

We will use angular-material once more as described in the preceding example. So, install and use the components as you see fit to style your application's UI:

npm install --save @angular/material @angular/animations @angular/cdk

We will use MatGridListModule to create our application's UI. After importing it in the main module, we can create the template as follows:

<mat-grid-list cols="2" rowHeight="2:1">
    <mat-grid-tile>
        <textarea (keyup)="codeChange()" [(ngModel)]="code"></textarea>
    </mat-grid-tile>
    <mat-grid-tile>
        <div>
            Result: {{result}}
        </div>
    </mat-grid-tile>
</mat-grid-list>

We are laying down two tiles; the first one contains the textarea to write the code and the second one displays the result generated.

We have bound the input area with ngModel, which is going to provide the two-way binding that we need between our view and the component. Further, we leverage the keyup event to trigger the method called codeChange(), which will be responsible for passing our expression into the worker.

The implementation of the codeChange() method will be relatively easy.

As the component loads, we will want to set up the worker so that it is not something that we have to repeat several times. So, imagine if there were a way in which you can set up something conditionally and perform an action only when you want it to. In our case, you can add it to the constructor or to any of the lifecycle hooks that denote what phase the component is in such as OnInit, OnContentInit, OnViewInit and so on, which are provided by Angular as follows:

this.worker = new Worker('scripts.bundle.js');

this.worker.addEventListener('message', (e) => {
 this.result = e.data;
});

Once initialized, we then use the addEventListener() method to listen for any new messages—that is, results coming from our worker.

Any time the code is changed, we simply pass that data to the worker that we have now set up. The implementation for this looks as follows:

codeChange() {
    this.worker.postMessage(this.code);
}

As you can note, the main application component is intentionally lean. We are leveraging workers for the sole reason that CPU-intensive operations can be kept away from the main thread. In this case, we can move all the logic including the validations into the worker, which is exactly what we have done.

Now that the app component is set and ready to send messages, the worker needs to be enabled to receive the messages from the main thread. To do that, add the following code to your worker.js file:

init();

function init() {
   self.addEventListener('message', function(e) {
      var code = e.data;

      if(typeof code !== 'string' || code.match(/.*[a-zA-Z]+.*/g)) {
         respond('Error! Cannot evaluate complex expressions yet. Please try
         again later');
      } else {
         respond(evaluate(convert(code)));
      }
   });
}

As you can see, we added the capability of listening for any message that might be sent to the worker and then the worker simply takes that data and applies some basic validation on it before trying to evaluate and return any value for the expression. In our validation, we simply rejected any characters that are alphabetic because we want our users to only provide valid numbers and operators. 

Now, start your application using the following command:

npm start

You should see the app come up at localhost:4200. Now, simply enter any code to test your application; for example, enter the following:

var a = 100;

You would see the following error pop up on the screen:

Now, let's get a detailed understanding of the algorithm that is in play. The algorithm will be split into two parts: parsing and evaluation.  A step-by-step breakdown of the algorithm would be as follows:

The input (anything that the user types) will be an expression in the infix notation, which is human-readable. Consider this for example:

(1 + 1) * 2

However, this is not something that we can evaluate as it is, so we convert it into a postfix notation or reverse polish notation. 

To convert an infix to a postfix notation is something that takes a little getting used to. What we have  is a watered-down version of that algorithm in Wikipedia, as follows:

Before we translate this into some code, let's briefly talk about the precedence and associativity of the operators, which is something that we need to predefine so that we can use it while we are converting the infix expression to postfix.

Precedence, as the name suggests, determines the priority of that particular operator whereas associativity dictates whether the expression is evaluated from left to right or vice versa in the absence of a parenthesis. Going by that, since we are only supporting simple operators, let's create a map of operators, their priority, and associativity:

var operators = {
    "^": {
        priority: 4,
        associativity: "rtl" // right to left
    },
    "*": {
        priority: 3,
        associativity: "ltr" // left to right
    },
    "/": {
        priority: 3,
        associativity: "ltr"
    },
    "+": {
        priority: 2,
        associativity: "ltr"
    },
    "-": {
        priority: 2,
        associativity: "ltr"
    }
};

Now, going by the algorithm, the first step is to tokenize the input string. Consider the following example:

(1 + 1) * 2

It would be converted as follows:

["(", "1", "+", "1", ")", "*", "2"]

To achieve this, we basically remove all extra spaces, replace all white spaces with empty strings, and split the remaining string on any of the *, ^, +, -, / operators and remove any occurrences of an empty string.

Since there is no easy way to remove all empty strings "" from an array, we can use a small utility method called clean, which we can create in the same file.

 This can be translated into code as follows:

function clean(arr) {
    return arr.filter(function(a) {
        return a !== "";
    });
}

So, the final expression becomes as follows:

expr = clean(expr.trim().replace(/\s+/g, "").split(/([\+\-\*\/\^\(\)])/));

Now that we have the input string split, we are ready to analyze each of the tokens to determine what type it is and take action accordingly to add it to the postfix notation output string. This is Step 2 of the preceding algorithm, and we will use a Stack to make our code more readable. Let's include the stack into our worker, as it cannot access the outside world. We simply convert our stack to ES5 code, which would look as follows:

var Stack = (function () {
   var wmkey = {};
   var items = new WeakMap();

   items.set(wmkey, []);

   function Stack() { }

   Stack.prototype.push = function (element) {
      var stack = items.get(wmkey);
      stack.push(element);
   };
   Stack.prototype.pop = function () {
      var stack = items.get(wmkey);
      return stack.pop();
   };
   Stack.prototype.peek = function () {
      var stack = items.get(wmkey);
      return stack[stack.length - 1];
   };
   Stack.prototype.clear = function () {
      items.set(wmkey, []);
   };
   Stack.prototype.size = function () {
      return items.get(wmkey).length;
   };
   return Stack;
}());

As you can see, the methods are attached to the prototype and voilà we have our stack ready.

Now, let's consume this stack in the infix to postfix conversion. Before we do the conversion, we will want to check that the user-entered input is valid, that is, we want to check that the parentheses are balanced. We will be using the simple isBalanced() method as described in the following code, and if it is not balanced we will return an error:

function isBalanced(postfix) {
   var count = 0;
   postfix.forEach(function(op) {
      if (op === ')') {
         count++
      } else if (op === '(') {
         count --
      }
   });

   return count === 0;
}

We are going to need the stack to hold the operators that we are encountering so that we can rearrange them in the postfix string based on their priority and associativity. The first thing we will need to do is check whether the token encountered is a number; if it is, then we append it to the postfix result:

expr.forEach(function(exp) {
    if(!isNaN(parseFloat(exp))) {
        postfix += exp + " ";
    }
});

Then, we check whether the encountered token is an open bracket, and if it is, then we push it to the operators' stack waiting for the closing bracket. Once the closing bracket is encountered, we group everything (operators and numbers) in between and pop into the postfix output, as follows:

expr.forEach(function(exp) {
    if(!isNaN(parseFloat(exp))) {
        postfix += exp + " ";
    }  else if(exp === "(") {
        ops.push(exp);
    } else if(exp === ")") {
        while(ops.peek() !== "(") {
            postfix += ops.pop() + " ";
        }
        ops.pop();
    }
});

The last (and a slightly complex) step is to determine whether the token is one of *, ^, +, -, /, and then we check the associativity of the current operator first. When it's left to right, we check to make sure that the priority of the current operator is less than or equal to the priority of the previous operator. When it's right to left, we check whether the priority of the current operator is strictly less than the priority of the previous operator. If any of these conditions are satisfied, we pop the operators until the conditions fail, append them to the postfix output string, and then add the current operator to the operators' stack for the next iteration.

The reason why we do a strict check for a right to left but not for a left to right associativity is that we have multiple operators of that associativity with the same priority. 

After this, if any other operators are remaining, we then add them to the postfix output string.

Putting together all the code discussed above, the final code for converting the infix expression to postfix looks like the following: 

function convert(expr) {
    var postfix = "";
    var ops = new Stack();
    var operators = {
        "^": {
            priority: 4,
            associativity: "rtl"
        },
        "*": {
            priority: 3,
            associativity: "ltr"
        },
        "/": {
            priority: 3,
            associativity: "ltr"
        },
        "+": {
            priority: 2,
            associativity: "ltr"
        },
        "-": {
            priority: 2,
            associativity: "ltr"
        }
    };


    expr = clean(expr.trim().replace(/\s+/g, "").split(/([\+\-\*\/\^\(\)])/));

    if (!isBalanced(expr) {
        return 'error';
    }    

    expr.forEach(function(exp) {
        if(!isNaN(parseFloat(exp))) {
            postfix += exp + " ";
        }  else if(exp === "(") {
            ops.push(exp);
        } else if(exp === ")") {
            while(ops.peek() !== "(") {
                postfix += ops.pop() + " ";
            }
            ops.pop();
        } else if("*^+-/".indexOf(exp) !== -1) {
            var currOp = exp;
            var prevOp = ops.peek();
            while("*^+-/".indexOf(prevOp) !== -1 && ((operators[currOp].associativity === "ltr" && operators[currOp].priority <= operators[prevOp].priority) || (operators[currOp].associativity === "rtl" && operators[currOp].priority < operators[prevOp].priority)))
            {
                postfix += ops.pop() + " ";
                prevOp = ops.peek();
            }
            ops.push(currOp);
        }
    });

    while(ops.size() > 0) {
        postfix += ops.pop() + " ";
    }
    return postfix;
}

This converts the infix operator provided into the postfix notation.

From here on, executing this postfix notation is fairly easy. The algorithm is relatively straightforward; you pop out each of the operators onto a final result stack. If the operator is one of *,^,+,-,/, then evaluate it accordingly; otherwise, keep appending it to the output string:

function evaluate(postfix) {
    var resultStack = new Stack();
    postfix = clean(postfix.trim().split(" "));
    postfix.forEach(function (op) {
        if(!isNaN(parseFloat(op))) {
            resultStack.push(op);
        } else {
            var val1 = resultStack.pop();
            var val2 = resultStack.pop();
            var parseMethodA = getParseMethod(val1);
            var parseMethodB = getParseMethod(val2);

            if(op === "+") {
                resultStack.push(parseMethodA(val1) + parseMethodB(val2));
            } else if(op === "-") {
                resultStack.push(parseMethodB(val2) - parseMethodA(val1));
            } else if(op === "*") {
                resultStack.push(parseMethodA(val1) * parseMethodB(val2));
            } else if(op === "/") {
                resultStack.push(parseMethodB(val2) / parseMethodA(val1));
            } else if(op === "^") {
                resultStack.push(Math.pow(parseMethodB(val2), 
                parseMethodA(val1)));
            }
       }
    });

    if (resultStack.size() > 1) {
        return "error";
    } else {
        return resultStack.pop();
    }
}

Here, we use some helper methods such as getParseMethod() to determine whether we are dealing with an integer or float so that we do not round any number unnecessarily.

Now, all we need to do is to instruct our worker to return the data result that it has just calculated. This is done in the same way as the error message that we return, so our init() method changes as follows: 

function init() {
    self.addEventListener('message', function(e) {
        var code = e.data;

        if(code.match(/.*[a-zA-Z]+.*/g)) {
            respond('Error! Cannot evaluate complex expressions yet. Please try
            again later');
        } else {
            respond(evaluate(convert(code)));
        }
    });
}