A Technology Blog About Code Development, Architecture, Operating System, Hardware, Tips and Tutorials for Developers.

Tuesday, September 20, 2016

Evaluate PreFix Expression

1:25:00 PM Posted by Satish Kumar , No comments
We have already written algorithm to convert infix expression to post fix expression. You can refer my previous post for the same. As we have already having a prefix expression and that is well known to computer, let's directly jump on to the algorithm.

Algorithm:
  1. Reverse the expression.
  2. Tokenize the expression depending on the delemeter.
  3. Perform the following operations on each token.
    1. If token is operand, push the token to the stack
    2. If token is operator.
      1. Do two pops on stack. First one being operand 1 and second one being operand 2.
      2. Create an expression operand 1 + token + operand 2 and evaluate. 
      3. Push the result in stack again.
  4. Pop the stack for the result.
Time Complexity : O(N^2)

Difference against the Post Fix Evaluation :
  1. We have to reverse in the first instance.
  2. In prefix evaluation we have to treat the first pop as operand 1 and second pop as operand 2 unlike post fix evaluation
Algorithm Execution:

Input Expression : + 1 * 2 3

Step 1 : + 1 * 2 3 => 3 2 * 1 +
Step 2 : Stack[3]
Step 3 : Stack[3, 2]
Step 4 : Stack[6]
Step 5 : Stack[6,1]
Step 5 : Stack[7] - Result

Time Complexity : O(N)


You can fork the source code and unit tests from github.

Evaluate Post Fix Expression

1:15:00 PM Posted by Satish Kumar , No comments
We have already written algorithm to convert infix expression to post fix expression. You can refer my previous post for the same. As we have already having a post fix expression and that is well known to computer, let's directly jump on to the algorithm.

Algorithm:

  1. Tokenize the expression depending on the delemeter.
  2. Perform the following operations on each token.
    1. If token is operand, push the token to the stack
    2. If token is operator.
      1. Do two pops on stack. First one being operand 2 and second one being operand 1.
      2. Create an expression operand 1 + token + operand 2 and evaluate. 
      3. Push the result in stack again.
  3. Pop the stack for the result.
Time Complexity : O(N)

Algorithm Execution:

Input Expression : 1 2 3 * +

Step 1 : Stack[1]
Step 3 : Stack[1, 2]
Step 4 : Stack[1,2,3]
Step 5 : Stack[1,6]
Step 5 : Stack[7] - Result

You can fork the source code and unit tests from github.

Infix to Prefix

11:26:00 AM Posted by Satish Kumar , No comments
In my previous post we evaluated the algorithm to convert a prefix expression to post fix expression. Infix to Post fix algorithm is going to be handy for writing the algorithm of Infix to Prefix. We just need few additional steps to do so. But before jumping on to the solution for computer program, let's first solve it in a mathematical way. 

Before just jumping on to the algorithm and implementation, let's start slow. I am going to convert a infix expression first in a traditional mathematical way and then will derive the algorithm using computer language. Let me start with a simple example.

Order Of Operation
  1. Parenthesis - ( ) { } [ ]
  2. Exponent (Right to left)
  3. Multiplication and Division (Left to Right)
  4. Addition and Subtraction (Left to Right)
Given Infix Expression : A + B * C

Steps:
  1. First manually put the parenthesis depending on the operator precedence.
  2. Then start evaluating from the inner most expression.
  3. Remove the parenthesis.
A + B * C -> A + ( B * C ) -> A + ( * B  C ) -> + A ( * B C )  + -> + A * B C

Final Result : + A * B C

Now let directly jump on to the computer algorithm. I will not be writing the infix to post fix algorithm here. Please refer my previous post for the same.

Algorithm:
  1. Reverse the input expression
  2. Change all open parenthesis to close and visa versa. 
  3. Run the infix to post fix algorithm
  4. Reverse the output
Time Complexity : 

Time Complexity of infix to post fix + O(n) + O(n) + O(n)
=>(O(n+m)) + O(m)) + O(n) + O(n) + O(n) where n =  no of tokens, m = stack size


You can also fork the code from github.

Infix to Post Fix

10:11:00 AM Posted by Satish Kumar , No comments
Before just jumping on to the algorithm and implementation, let's start slow. I am going to convert a infix expression first in a traditional mathematical way and then will derive the algorithm using computer language. Let me start with a simple example.

Order Of Operation
  1.  Parenthesis - ( ) { } [ ]
  2.  Exponent (Right to left)
  3. Multiplication and Division (Left to Right)
  4. Addition and Subtraction (Left to Right)
Given Infix Expression : A + B * C

Steps:
  1. First manually put the parenthesis depending on the operator precedence.
  2. Then start evaluating from the inner most expression.
  3. Remove the parenthesis.
A + B * C -> A + ( B * C ) -> A + ( B  C * ) -> A ( B C * )  + -> A B C * +

Final Result : A B C * +

Now let's solve the problem using computer language and we are going to take the help of the stack to solve this problem. Why we opted for a stack ADT? Good question and I believe, the next explanation will clarify your answer. So let's not jump on that question now. 

Given Infix Expression : A + B * C

We are going to use the following use the following components for the algorithm.
  1. Stack
  2. String
Algorithm :
  1. Tokenize the expression depending on the delemeter.
  2. Perform the steps for each of the token
    1. If token is an operand append to the result string
    2. If token is an operator peek the stack, check if operator and check for the operator precedence
      1. pop the stack till stack has operator precedence greater than equal to token precedence and append that to string.
      2. else push the operator to the stack
    3. If you find an open parenthesis, push that to the stack.
    4. If you find an closed parenthesis, pop and append to the string till you get a open parenthesis. Then pop the open parenthesis too.
  3. Pop the entire stack and append that to result string.
Time Complexity : O(n+m)) + O(m) where n =  no of tokens, m = stack size

Execution of algorithm:

Step 1 : String : A :: Stack : []
Step 2 : String : A :: Stack : [+]
Step 3 : String : AB :: Stack : [+]
Step 4 : String : AB :: Stack : [+, *]
Step 5 : String : ABC :: Stack : [+,*]
Step 6 : String : ABC*+ :: Stack : []

I took a very easy expression to keep the post simple and more understandable. You can apply the same algorithm to process your complex expressions. Now it's time to convert this algorithm steps to a program. I am using java to do so.


The complete program with github can be forked here

Tuesday, February 12, 2013

OAuth2 - In a Simple Way

11:40:00 PM Posted by Satish Kumar , , , , , 4 comments
Last week I started playing with OAuth 2.0. I started with a github project called spring-security-oauth. I checked the sample OAuth 2 provider sparklr and OAuth 2 client tonr. But I could not get much from the sample example and the documentation provided. I explored a bit in the internet and finally could able to conclude some thing. I created a sample provider and checked all authorization on that. Now, I am here to explain different aspects of OAuth 2.0 from the practical point of view. I will try my best to present a modular and easy explanation here.


Many services such as Facebook, Github, and Google have already implemetated OAuth 2.0. That is why today most of the web sites using google/ facebook for authentication and authorization. They work as resource server, from where other clients fetch profile informations.

This post is an attempt to describe OAuth 2.0 in a simplified format to help developers and service providers implement the protocol.

I will be covering the following topics in this article.

1. Entities
2. Creating an Application
3. Authorization
a. Web Server Apps
b. Browser-Based Apps
c. Mobile Apps
d. Others
4. Accessing Resources
5. Resources


OAuth 2 Entities
OAuth 2 Entites


Entities:

OAuth Server:
This is also known as OAuth Provider. It's whole responsibility is to authenticate and authorize user/ client and manage the tokens. 

The Third-Party Application:
Third-Party Application popularly known as client, is going to attempt to get access to the user's account. It needs to get permission from the user, before it can do so. This could be a web server based application, browser based application, desktop application, mobile/tablet application or some smart devices like google Goggles and smart televisions. 

Resource Server:
The API popularly known as Resource Server, from where the data will be fetched out or served. This could be the SOAP or REST based service providers.

The User:
The User popularly known as Resource Owner, who gives access to access the resource.

Creating an Application:

Before you can begin the OAuth process, you must first register a new app with the service/provider. When registering a new app, you usually register basic information such as application clint id, secret, authorized-grant-types etc. In addition, you must register a redirect URI to be used for redirecting users to for web server, browser-based, or mobile apps.

Redirect URIs:
The service will only redirect users to a registered URI, which helps prevent some attacks. Any HTTP redirect URIs must be protected with SSL security, so the service will only redirect to URIs beginning with "https". This prevents tokens from being intercepted during the authorization process.

Client ID and Secret:
After registering your app, you will be having your client ID and a client secret. The client ID is considered public information, and is used to build login URLs, or included in Javascript source code on a page. The client secret must be kept confidential. If a deployed app cannot keep the secret confidential, such as Javascript or native apps, then the secret is not used.

Authorization:

The first step of OAuth 2 is to get authorization from the user. For browser-based or mobile apps, this is usually accomplished by displaying an interface provided by the service to the user.

OAuth 2 provides several grant types for different use cases. The grant types defined are:

Authorization Code for apps running on a web server
Implicit for browser-based or mobile apps
Password for logging in with a username and password
Client credentials for application access

Web Server Apps
Web apps are written in a server-side language and run on a server where the source code of the application is not available to the public.

Authorization request:

http://localhost:8080/oauth2/oauth/authorize?response_type=code&client_id=easylocate&scope=read&redirect_uri=http://localhost:8080/web

After accepting the access. the page will be redirected to the redirect uri with the authorization code.

http://localhost:8080/web/?code=t7ol7D

Now it is time to exchange the authorization code to get the access token.

http://localhost:8080/oauth2/oauth/token?grant_type=authorization_code&code=t7ol7D&redirect_uri=http://localhost:8080/web&client_id=easylocate&client_secret=secret

The OAuth server replies with the access token

1
2
3
4
5
6
7
{
  "access_token": "372c3458-4067-4b0b-8b77-7930f660d990",
  "token_type": "bearer",
  "refresh_token": "ce23c924-3f28-456c-a112-b5d02162f10c",
  "expires_in": 37364,
  "scope": "read"
}

In case of wrong authorization code, Oauth server replies error.

1
2
3
4
{
  "error": "invalid_grant",
  "error_description": "Invalid authorization code: t7olD"
}

Security: Note that the service should require apps to pre-register their redirect URIs. Or else there will be a mismatch.

Browser-Based Apps & Mobile Apps:
Browser-based apps run entirely in the browser after loading the source code from a web page. Since the entire source code is available to the browser, they cannot maintain the confidentiality of their client secret, so the secret is not used in this case.

Authorization request:

http://localhost:8080/oauth2/oauth/authorize?response_type=token&client_id=easylocate&redirect_uri=http://localhost:8080/web&scope=read

After accepting the access. the page will be redirected to the redirect uri with the token.

http://localhost:8080/web/#access_token=372c3458-4067-4b0b-8b77-7930f660d990&token_type=bearer&expires_in=37026

That's it, there's no other steps! At this point, some Javascript code can pull out the access token from the fragment (the part after the #) and begin making API requests.

If there is an error, you will instead receive an error in the URI fragment, such as:

http://localhost:8080/web/#error=invalid_scope&error_description=Invalid+scope%3A+rea&scope=read+write

Password Based:
OAuth 2 also provides a password grant type which can be used to exchange a username and password for an access token directly. Since this obviously requires the application to collect the user's password, it should only be used by apps created by the service itself. For example, the native Twitter app could use this grant type to log in on mobile or desktop apps.

To use the password grant type, simply make a POST request like the following. I am using the curl tool to demonstrate the POST request. You may use any rest client.

curl -i -X POST -d "client_id=easylocate&grant_type=password&username=admin&password=admin&client_secret=secret" http://localhost:8080/oauth2/oauth/token

The server will get back with the token

1
2
3
4
5
6
7
{
  "access_token": "4e56e9ec-2f8e-46b4-88b1-5d06847909ad",
  "token_type": "bearer",
  "refresh_token": "7e14c979-7039-49d0-9c5d-854efe7f5b38",
  "expires_in": 36133,
  "scope": "read write"
}

Client Credential Based:
Client credentals based authorization is used for server to server application access. I am just showing a POST request using the curl tool.

curl -i -X POST -d "client_id=easylocate&grant_type=client_credentials&client_secret=secret" http://localhost:8080/oauth2/oauth/token

Server will get back with the access token

1
2
3
4
5
6
{
  "access_token": "9cd23bef-ae56-46b0-82f5-b9a8f78da569",
  "token_type": "bearer",
  "expires_in": 43199,
  "scope": "read write"
}

Accessing Resources:

Once you are been authenticated and got the access token, you can provide the the access token to access the protected resources.

1
curl -i -H "Authorization: Bearer 4e56e9ec-2f8e-46b4-88b1-5d06847909ad" http://localhost:8080/oauth2/users

I have created my OAuth2 server/provider using spring oauth2 api. I will be creating deferent types of clients and services to demonstrate more. I am not that good in mobile app development, appreciate if some one fork the project and add sample mobile applications. I have shared the code at GitHub.

Resources:

Tuesday, December 25, 2012

@RequestParam - JAX-RS

11:38:00 PM Posted by Satish Kumar , , , , , , No comments
For this tutorial, I will be using the workspace created in my tutorial RESTful Web Service with Spring 3.1. So I suggest you to read RESTful Web Service with Spring 3.1, before start reading this tutorial. In JAX-RS, you can use @RequestParam annotation to inject URI query parameter into Java method and in this tutorial I will demonstrate how to use this using Spring 3.1.0.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package com.techiekernel.service;

import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.ResponseBody;

import com.techiekernel.model.FooBar;
import com.techiekernel.model.FooBarSet;

/**
 * This exmaple has been created to demonstrate the @RequestParam for JAX-RS
 * 
 * @author satish
 * 
 */
@Controller
@RequestMapping("/foobaresample3")
public class FooBarServiceExample3 {

 static FooBarSet fooBarSet;

 static {
  fooBarSet = new FooBarSet();
  FooBar foobar = null;
  for (int i = 0; i < 10; i++) {
   foobar = new FooBar(i, "TechieKernel" + i);
   fooBarSet.add(foobar);
  }
 }

 @RequestMapping(method = RequestMethod.GET, headers = "Accept=application/xml, application/json", produces = {
   "application/json", "application/xml" })
 @ResponseBody
 public FooBar getFoobar(@RequestParam int foobarId) {
  for (FooBar foobar : fooBarSet) {
   if (foobar.getId() == foobarId)
    return foobar;
  }
  return null;
 }
 
 @RequestMapping(value= "/name" ,method = RequestMethod.GET, headers = "Accept=application/xml, application/json", produces = {
   "application/json", "application/xml" })
 @ResponseBody
 public FooBar getFoobar(@RequestParam int foobarId, @RequestParam String name) {
  for (FooBar foobar : fooBarSet) {
   if (foobar.getId() == foobarId && foobar.getName().equalsIgnoreCase(name))
    return foobar;
  }
  return null;
 }
}

Now it is time to test the web service for different inputs..

1
2
3
curl -i "http://springmvc-rest.cloudfoundry.com/foobaresample3?foobarId=1" -X GET 

curl -i "http://springmvc-rest.cloudfoundry.com/foobaresample3/name?foobarId=1&name=techiekernel1" -X GET

I have deployed the application in cloud space and it is available for you to test. You can use the above URLs to test from your side..

Source Code:

You can pull the source code from GitHub

@PathParam - JAX-RS

11:09:00 PM Posted by Satish Kumar , , , , , , 2 comments
For this tutorial, I will be using the workspace created in my tutorial RESTful Web Service with Spring 3.1. So I suggest you to read RESTful Web Service with Spring 3.1, before start reading this tutorial. In JAX-RS, you can use @PathParam to inject the value of URI parameter that defined in @Path expression, into Java method and in this tutorial I will demonstrate how to use this using Spring 3.1.0


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package com.techiekernel.service;

import java.util.Iterator;

import org.springframework.stereotype.Controller;
import org.springframework.validation.annotation.Validated;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.ResponseBody;

import com.techiekernel.model.FooBar;
import com.techiekernel.model.FooBarSet;

/**
 * This exmaple has been created to demonstrate the @path for JAX-RS
 * 
 * @author satish
 * 
 */
@Controller
@RequestMapping("/foobaresample2")
public class FooBarServiceExample2 {

  static FooBarSet fooBarSet;

  static {
    fooBarSet = new FooBarSet();
    FooBar foobar = null;
    for (int i = 0; i < 10; i++) {
      foobar = new FooBar(i, "TechieKernel" + i);
      fooBarSet.add(foobar);
    }
  }

  /**
   * Normal URI Mapping with parameter
   * @param foobarId
   * @return
   */
  @RequestMapping(value = "/{foobarId}", method = RequestMethod.GET, headers = "Accept=application/xml, application/json", produces = {
      "application/json", "application/xml" })
  @ResponseBody
  public FooBar getFoobar(@PathVariable int foobarId) {
    for (FooBar foobar : fooBarSet) {
      if (foobar.getId() == foobarId)
        return foobar;
    }
    return null;
  }
  
  @RequestMapping(value = "/{foobarId}/{name}", method = RequestMethod.GET, headers = "Accept=application/xml, application/json", produces = {
      "application/json", "application/xml" })
  @ResponseBody
  public FooBar getFoobar(@PathVariable int foobarId, @PathVariable String name) {
    for (FooBar foobar : fooBarSet) {
      if (foobar.getId() == foobarId && foobar.getName().equalsIgnoreCase(name))
        return foobar;
    }
    return null;
  }
}

Now it is time to test the web service for different inputs..

1
2
3
curl -i "http://springmvc-rest.cloudfoundry.com/foobaresample2/1" -X GET 

curl -i "http://springmvc-rest.cloudfoundry.com/foobaresample2/1/techiekernel1" -X GET

I have deployed the application in cloud space and it is available for you to test. You can use the above URLs to test from your side..

Source Code:

You can pull the source code from GitHub