Algorithm for Infix to Postfix
One of the applications of stack is in the evaluation of arithmetic expressions. To evaluate any arithmetic expression we convert the infix expression to postfix. Then evaluate the postfix expression using a stack. In this article I would define the standard algorithm for this.
Define a stack
Go through each character in the string
If it is between 0 to 9, append it to output string.
If it is left brace push to stack
If it is operator *+-/ then
If the stack is empty push it to the stack
If the stack is not empty then start a loop:
If the top of the stack has higher precedence
Then pop and append to output string
Else break
Push to the stack
If it is right brace then
While stack not empty and top not equal to left brace
Pop from stack and append to output string
Finally pop out the left brace.
If there is any input in the stack pop and append to the output string.
Here is the code for conversion from infix to postfix.
public static string ConvertInfixToPostfix(string infix)
{
int length = infix.Length;
Stack<char> stack = new Stack<char>();
StringBuilder postfix = new StringBuilder();
for (int i = 0; i < length; i++)
{
if ((infix[i] >= '0') && (infix[i] <= '9'))
{
postfix.Append(infix[i]);
}
else if (infix[i] == '(')
{
stack.Push(infix[i]);
}
else if ((infix[i] == '*') || (infix[i] == '+') || (infix[i] == '-') || (infix[i] == '/'))
{
while ((stack.Count > 0) && (stack.Peek() != '('))
{
if (ComparePrecedence(stack.Peek(), infix[i]))
{
postfix.Append(stack.Pop());
}
else
{
break;
}
}
stack.Push(infix[i]);
}
else if (infix[i] == ')')
{
while ((stack.Count > 0) && (stack.Peek() != '('))
{
postfix.Append(stack.Pop());
}
if (stack.Count > 0)
stack.Pop(); // popping out the left brace '('
}
else
{
}
}
while (stack.Count > 0)
{
postfix.Append(stack.Pop());
}
return postfix.ToString();
}
private static bool ComparePrecedence(char top, char p_2)
{
if (top == '+' && p_2 == '*') // + has lower precedence than *
return false;
if (top == '*' && p_2 == '-') // * has higher precedence over -
return true;
if (top == '+' && p_2 == '-') // + has same precedence over +
return true;
return true;
}
public static int EvaluatePostFix(string postfix)
{
Stack<int> resultStack = new Stack<int>();
int length = postfix.Length;
for (int i = 0; i < length; i++)
{
if ((postfix[i] == '*') || (postfix[i] == '+') || (postfix[i] == '-') || (postfix[i] == ''))
{
int result = ApplyOperator(resultStack.Pop(), resultStack.Pop(), postfix[i]);
resultStack.Push(result);
}
else if ((postfix[i] >= '0') || (postfix[i] <= '9'))
{
resultStack.Push((int)(postfix[i] - '0'));
}
else
{
}
}
return resultStack.Pop();
}
private static int ApplyOperator(int p, int p_2, char p_3)
{
switch (p_3)
{
case '+':
return p_2 + p;
case '-':
return p_2 - p;
case '*':
return p_2 * p;
case '/':
return p_2 / p;
default:
return -1;
}
return -1;
}
ODATA enables the creation of RESTful based data services that allow resources identified using URL and defined in a data model to be published and edited by web clients using HTTP messages.
OData is the web-based equivalent of ODBC, OLEDB, ADO.NET and JDBC.
As more data-oriented web APIs come online, each team responsible for the design of each web API is confronted by the same kinds of questions, and each team answers these in their own particular way
Increasingly, “RESTful” is a design goal of web APIs. Great…but what does that mean?
How do you expose the data, the relationships between the entities inside the model, and what should the querying syntax look like?
Unfortunately, there are as many answers to these questions as there are RESTful web APIs.
Below is diagram of various OData Producers and Consumers.
OData is built on top of ATOM. ATOM is simple way of exposing ‘feed’ of data, each distinct piece of which is called ‘entry’. Atom originated in a world of bloggers to keep the readers upto date.
At the core of OData are feeds, which are Collections of typed Entries.
Each entry represents a structured record with a key that has a list of Properties of primitive or complex types. Entries can be part of a type hierarchy and may have related entries and related feeds through Links.
Every OData service expose Service Document and Service Meta Document. A Service Document lists all the top-level feeds so clients can discover them and find out the addresses of each of them. The service document is available at the Service Root URI and may be formatted in ATOM or JSON. A Service Meta Document describes the data model (i.e.structure and organization of all the resources) exposed as HTTP endpoints by the service. fadfa
OData provides the following benefits :
1. Simple and Uniform way of sharing data at the protocol level.
2. Enables broad integration across products and breaks data silos.
3. All you need is Http stack to integrate with any OData producer.
A simple, uniform way of sharing data at the protocol level, and in a way that truly enables the lowest possible bar of entry, is key to enable broad integration across products and break data silos that form around applications.
More details on OData at : www.odata.org and www.odataprimer.com