Solving the parentheses problem in arithmetic expressions

So a little while ago I rewrote an expression evaluator I wrote in college for this crazy idea called ‘JMScript’ (JM, like my name!….), which was meant to be a python interpreter written in pure C#. I ended up getting a lot of functionality working, but at the same time added a ton of complexity. I decided not too long ago that I would strip it down to the good parts into a new library I’m calling JMExpressionEvaluator. In this library I’m using a technique to handle the parentheses problem when dealing with arithmetic expressions. So here’s the rundown.

The Algorithm

The idea behind it goes like this:

  1. Get an initial count of parentheses in the expression.
  2. If there’s an odd amount, throw an appropriate exception.
  3. Otherwise, while we have parentheses to work with, get the outer most parenthetical expression.
    • This is defined as the expression inside the farthest left ‘(‘ and farthest right ‘)’.
    • (5 + 3 * (2 – 1)): 5 + 3 * (2 – 1) would be the outer most parenthetical expression.
  4. Once we have that expression, recursively break it down (nested-level) until no more parentheses exist.
  5. If any more parentheses exist in the expression (same-level), continue to break them down in a loop.
  6. Using that new expression, solve it.

And that’s it in a nutshell. It was really interesting working through this, and the solution that made the most sense to me was the recursive one with an outer loop. Speed wise my unit tests run < 1ms, with some expressions pretty lengthy, so I'd imagine for most common cases performance would be good. Below is a code sample showing how I'm doing this, and on my portfolio is the full source and a dll that can be downloaded.

int parenthesesAmount = arithmetic.GetCharCountOutsideQuotes(expression, '(') + arithmetic.GetCharCountOutsideQuotes(expression, ')');
int doubleQuoteAmount = arithmetic.GetCharCountOutsideQuotes(expression, '"');

if (doubleQuoteAmount % 2 != 0)
{
	string message = string.Format("Odd number of double quotes found: {0}. Are you missing a double quote?", doubleQuoteAmount);
	throw new ArithmeticException(message);
}
else if (parenthesesAmount % 2 != 0)
{
	string message = string.Format("Odd number of parentheses found: {0}. Are you missing a parentheses?", parenthesesAmount);
	throw new ArithmeticException(message);
}

while (parenthesesAmount != 0)
{
	expression = arithmetic.GetOuterMostParentheticalExpression(expression, Evaluate);
	parenthesesAmount = arithmetic.GetCharCountOutsideQuotes(expression, '(') + arithmetic.GetCharCountOutsideQuotes(expression, ')');
}

Helper methods (combined here, but in separate classes in source)

internal int GetCharCountOutsideQuotes(string original, char ch)
{
	int result = 0;
	bool inQuote = false;
	char curQuote = char.MinValue;

	for (int i = 0; i < original.Length; i++)
	{
		if (JMUtility.CheckQuotes(original, i, curQuote))
		{
			curQuote = original[i];
			inQuote = !inQuote;
			if (!inQuote)
				curQuote = char.MinValue;
			if (curQuote == ch)
				result++;
		}
		if (!inQuote)
		{
			if (original[i] == ch)
				result++;
		}
	}

	return result;
}

internal string GetOuterMostParentheticalExpression(string expression, Func<string, JMExpressionResult> action)
{
	int start = expression.IndexOfOutsideQuotes('(') + 1; int length = GetParentheticalLength(expression); // always default to non same level
	if (length > expression.Length || start == 0) 
	{
		string message = string.Format("Couldn't get parenthetical expression for {0}.", expression);
		throw new ArgumentException(message, "expression");
	}
	string outer = expression.Substring(start, length - start);
	return expression.ReplaceFirst("(" + outer + ")", action(outer).Value);
}

internal static int IndexOfOutsideQuotes(this string str, char ch, int startIndex = 0) 
{
	int result = -1;
	bool inQuote = false;
	char curQuote = char.MinValue;

	for (int i = startIndex; i < str.Length; i++) 
	{
		if (JMUtility.CheckQuotes(str, i, curQuote)) 
		{
			curQuote = str[i];
			inQuote = !inQuote;
			if (!inQuote) 
                            curQuote = char.MinValue;
		}
		if(!inQuote)
		{
			if (str[i] == ch) 
			{
				result = i;
				break;
			}
		}
	}

	return result;
}

internal int GetParentheticalLength(string str)
{
	int result = 0, leftCount = 0;
	char curQuote = char.MinValue;
	bool inQuote = false;
	for (int i = 0; i < str.Length; i++)
	{
		if (JMUtility.CheckQuotes(str, i, curQuote))
		{
			curQuote = str[i];
			inQuote = !inQuote;
		}
		if (!inQuote)
		{
			if (str[i] == '(') { leftCount++; }
			else if (str[i] == ')')
			{
				leftCount--;
				if (leftCount == 0)
				{
					result = i;
					break;
				}

			}
		}
	}
	return result;
}

internal static string ReplaceFirst(this string text, string search, string replace)
{
	if (search == null || replace == null || text == null) 
		return text;
	int pos = text.IndexOf(search); // Don't use outside quotes index check. Use it on the input instead to pass in the right search string
	if (pos < 0)
		return text;
	return text.Substring(0, pos) + replace + text.Substring(pos + search.Length);
}

internal static bool CheckQuotes(string line, int index, char curQuote)
{
	char ch = line[index];
	char pChar = index - 1 >= 0 ? line[index - 1] : char.MinValue;
	if (pChar == '\\')
		return false; // skip over escaped quotes
	else if (curQuote == char.MinValue) 
		return ch == '"'; // default
	else 
		return ch == curQuote; // otherwise a chosen curQuote
}

Quick Note: The Evaluate method used in the call to GetOuterMostParentheticalExpression is just the starting point for the expression evaluator.

Wrapping Up

Looking back at this I can see a few areas I could refactor that might help. Instead of just replacing the first instance, I could replace all occurrences of the expression solved. In that way we’re able to optimize even just a little bit more. For now this works pretty well, having passed over 130 unit tests so far. I’m sure I’m still missing cases, but enough are covered with error handling to warrant real use.

So hopefully this has been informative, if you’ve enjoyed reading please leave a comment below or see if I’ve made any mistakes or a better way of doing this I would love to hear it, thanks!

Connect to Gmail via POP using C# .NET

Setup

First you need to do two things to get your gmail account ready:

1) Enable POP communication if not already. You can do this by logging into gmail and going to settings (the gear in the top-right corner -> Settings), Forwarding and POP/IMAP, and enabling it there.
2) Enable less safe application communication. You can do this visiting this link and choosing to enable.

Using TcpClient to connect

The class:

internal class Pop3Client : IDisposable
{
	private readonly string mailServer;
	private readonly int port;
	private SslStream SecureStream;
	private StreamReader NetReader;

	internal Pop3Client(string mailServer, int port) 
	{
		this.mailServer = mailServer;
		this.port = port;
	}

	internal void Connect() 
	{
		var client = new TcpClient(mailServer, port);
		SecureStream = new SslStream(client.GetStream());
		SecureStream.AuthenticateAsClient(mailServer);
		NetReader = new StreamReader(SecureStream);
		var result = NetReader.ReadLine(); // Writes "+OK Gpop ready" on success
		Console.WriteLine(result);
	}

	internal void Login(string userName, string password) 
	{
		var user = Encoding.UTF8.GetBytes(string.Format("USER {0}{1}", userName, Environment.NewLine));
		var pw = Encoding.UTF8.GetBytes(string.Format("PASS {0}{1}", password, Environment.NewLine));
		SecureStream.Write(user);
		var result = NetReader.ReadLine(); // Writes "+OK send PASS" on success
		Console.WriteLine(result);
		SecureStream.Write(pw);
		result = NetReader.ReadLine(); // Writes "+OK Welcome." on success
		Console.WriteLine(result);
	}

	internal void RetrieveMessage(int messageNumber) 
	{
		var cmd = Encoding.UTF8.GetBytes(string.Format("RETR {0}{1}", messageNumber, Environment.NewLine));
		SecureStream.Write(cmd);
		var cmdResult = NetReader.ReadLine(); // Writes "+OK message follows" on success
		string line = null;
		var result = new StringBuilder();
		Console.WriteLine(NetReader.CurrentEncoding); 
		while (line != ".") 
		{
			line = NetReader.ReadLine(); // Read in each line 
			result.Append(line + Environment.NewLine); // And append it to our result
		}

		Console.WriteLine(result);
	}

	public void Dispose()
	{
		if (SecureStream != null)
			SecureStream.Dispose();
		if (NetReader != null)
			NetReader.Dispose();
	}
}

Usage

using (var client = new Pop3Client("pop.gmail.com", 995)) 
{
	client.Connect();
	client.Login("yourEmail@gmail.com", "yourPassword");
	client.RetrieveMessage(1);

	Console.WriteLine(client);
	Console.ReadLine();
}

When connecting via POP to Gmail, we need the mail server, port, and in this case I’m using the TcpClient class for communication and the SslStream class for authentication. Optionally I’ve included the StreamReader class to assist in reading, though you could use the SslStream to achieve the same effect.

So basically the process is simple: You write a command to the server, and receive a response. Whenever you write, make sure to include a newline character to complete it. I’m using UTF8 Encoded bytes to write, and then just reading that data back. The POP commands I’m using here are:

Commands

USER
PASS
RETR

The responses always start with one of the following, depending on success/failure

+OK
-ERR

One last thing. When retrieving a message, the returned message will have some sort of encoding. Quoted printable is a common one, and in order to get the complete message I would recommend decoding the message once you return it. I found the method here for decoding was effective for what I needed, and I recommend it for anyone else who needs it.

Copied here in case it gets taken down or removed (from www.dpit.co.uk)

private string DecodeQuotedPrintable(string input)  
{  
	var occurences = new Regex(@"(=[0-9A-Z][0-9A-Z])+", RegexOptions.Multiline);  
	var matches = occurences.Matches(input);  
	foreach (Match m in matches)  
	{  
		byte[] bytes = new byte[m.Value.Length / 3];  
		for (int i = 0; i < bytes.Length; i++)  
		{  
			string hex = m.Value.Substring(i * 3 + 1, 2);  
			int iHex = Convert.ToInt32(hex, 16);  
			bytes[i] = Convert.ToByte(iHex);  
		}

		input = input.Replace(m.Value, Encoding.Default.GetString(bytes));  
	}
  
	return input.Replace("=rn", "");  
}  

Wrapping Up

This same technique can be applied for IMAP as well with only a little tweaking. You’d need the server name, port, and instead of POP commands just use IMAP commands.

So hopefully this has been informative, if you’ve enjoyed reading please leave a comment below or see if I’ve made any mistakes or a better way of doing this I would love to hear it, thanks!

Using C# .NET to retrieve business data from Yelp

Yelp is a little different than Yellow Pages or Yahoo Local. For starters they only return data in JSON format. We’ll handle this and its other requirements with two libraries: SimpleOAuth.NET and JSON.NET. Both packages can be installed via NuGet.

Setup: Get your api keys

Start by registering with Yelp to get your api keys we’ll use to retrieve the json data.

You’ll need the following four keys:

  • Consumer Key
  • Consumer Secret
  • Access Token
  • Access Token Secret

Once you have your keys, the next step is to install the SimpleOAuth.NET and JSON.NET packages linked earlier. The easiest way is to use NuGet in Visual Studio. Once both are installed, the last thing to do is to get your web request url. For this post I’m going to use the following:

http://api.yelp.com/v2/business/tasty-subs-and-pizza-sunnyvale-3

Retrieve the JSON data and parsing the contents

The container class:

internal class YelpResult
{
	internal bool IsClaimed { get; set; }
	internal decimal Rating { get; set; }
	internal int ReviewCount { get; set; }
	internal string Name { get; set; }
	internal string Url { get; set; }
	internal string Phone { get; set; }
	internal IEnumerable<string> Categories { get; set; }
	internal string DisplayPhone { get; set; }
	internal bool IsClosed { get; set; }
	internal string City { get; set; }
	internal string Address { get; set; }
	internal string Zip { get; set; }
	internal string Country { get; set; }
	internal decimal Latitude { get; set; }
	internal decimal Longitude { get; set; }
	internal string State { get; set; }
}

The code:

internal YelpResult GetYelpReviews(string businessId)
{
	string url = string.Format("http://api.yelp.com/v2/business/{0}", businessId);
	var uriBuilder = new UriBuilder(url);
	const string consumerKey = ""; // Your consumer key
	const string consumerSecret = ""; // Your consumer secret
	const string token = ""; // Your token
	const string tokenSecret = ""; // Your token secret

	var request = WebRequest.Create(uriBuilder.ToString());
	request.Method = "GET";
	request.SignRequest(
		new Tokens
		{
			ConsumerKey = consumerKey,
			ConsumerSecret = consumerSecret,
			AccessToken = token,
			AccessTokenSecret = tokenSecret
		}).WithEncryption(EncryptionMethod.HMACSHA1).InHeader();

	JObject result;

	using (var response = (HttpWebResponse)request.GetResponse()) 
	{
		using (var stream = new StreamReader(response.GetResponseStream(), Encoding.UTF8))
		{
			result = JObject.Parse(stream.ReadToEnd());
		}
	}

	var location = result.Value<JObject>("location");
	var coordinate = location.Value<JObject>("coordinate");
	var address = location.Value<JArray>("address").Children().Select(jt => jt.Value<string>());

	return new YelpResult
	{
		IsClaimed = result.Value<bool>("is_claimed"),
		Rating = result.Value<decimal>("rating"),
		ReviewCount = result.Value<int>("review_count"),
		Name = result.Value<string>("name"),
		Url = result.Value<string>("url"),
		Phone = result.Value<string>("phone"),
		Categories = result.Value<JArray>("categories").Values<JArray>().Children().Select(jt => jt.Value<string>()),
		DisplayPhone = result.Value<string>("display_phone"),
		IsClosed = result.Value<bool>("is_closed"),
		City = location.Value<string>("city"),
		Address = string.Join(" ", address),
		Zip = location.Value<string>("postal_code"),
		Country = location.Value<string>("country_code"),
		Latitude = coordinate.Value<Decimal>("latitude"),
		Longitude = coordinate.Value<Decimal>("longitude"),
		State = location.Value<string>("state_code")
	};
}

So here we’re using JSON.NET to parse the data we’ve retrieved by making a web request with SimpleOAuth.NET. First we sign the request with our tokens, make our request, and return our data into a JObject. From there, using JSON.NET we parse each value and return the result.

Wrapping Up

So hopefully this has been informative, if you’ve enjoyed reading please leave a comment below or see if I’ve made any mistakes or a better way of doing this I would love to hear it, thanks!

Using C# .NET to retrieve business data from Google Places

The Google Places Api allows us to retrieve business data in either xml or json format. In this post I’m going to use the xml format, and go through what we need to do.

Setup: Get PlaceId, Api Key and web request url

First you need to visit the Google developers console, sign in, create a project, enable the google places api, and add a server key credential. Once you have your api key from this, next you need to format your url. For this post I’m going to use the following link, but feel free to use your own:

https://maps.googleapis.com/maps/api/place/details/xml?placeid=ChIJN1t_tDeuEmsRUsoyG83frY4&key={apiKey}

Replace {apiKey} with your own. Here I’m specifying that I want it formatted into xml, but you can choose json if you like.

Retrieving the xml and parsing the contents

The container classes:

internal class GooglePlacesResult
{
	internal string Name { get; set; }
	internal string Address { get; set; }
	internal string PhoneNumber { get; set; }
	internal string City { get; set; }
	internal string State { get; set; }
	internal string Country { get; set; }
	internal string Zip { get; set; }
	internal decimal Latitude { get; set; }
	internal decimal Longitude { get; set; }
	internal decimal Rating { get; set; }
	internal string Url { get; set; }
	internal string InternationalPhoneNumber { get; set; }
	internal IEnumerable<GooglePlacesReview> Reviews { get; set; }
	internal bool OpenNow { get; set; }
	internal IEnumerable<string> OpenHours { get; set; }
	internal int UtcOffset { get; set; }
	internal int UserRatingsTotal { get; set; }
}

internal class GooglePlacesReview 
{
	internal DateTime ReviewDate { get; set; }
	internal string ReviewText { get; set; }
	internal string AuthorName { get; set; }
	internal decimal Rating { get; set; }
	internal string Language { get; set; }
}

The extension method:

internal static T TryParseValue<T>(this string s) where T : struct
{
	var method = typeof(T).GetMethod(
		"TryParse",
		new []{typeof(string), typeof(T).MakeByRefType()}
		);
	T result = default(T);
	var parameters = new object[] { s, result };
	method.Invoke(null, parameters);
	return (T)parameters[1];
}

Also a method to convert an unix time value to a DateTime:

private DateTime FromUnixTime(long unixTime)
{
	var epoch = new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc);
	return epoch.AddSeconds(unixTime);
}

The code:

internal GooglePlacesResult GetGooglePlacesReviews(string placeId)
{
	string apiKey = ""; // Your api key
	string url = string.Format(@"https://maps.googleapis.com/maps/api/place/details/xml?placeid={0}&key={1}", placeId, apiKey);
	XDocument doc = XDocument.Load(url);
	var businessResults = doc.Root.Element("result");
			
	var addressComponents = businessResults.Elements("address_component").Where(e => e.Element("type") != null);
	var street = businessResults.Element("vicinity").Value;
	var cityTypes = new[] { "locality", "sublocality", "sublocality_level_1", "sublocality_level_2", "sublocality_level_3", "sublocality_level_4", "sublocality_level_5" };
	var stateTypes = new[] { "administrative_area_level_1" };
	var countryTypes = new[] { "country" };
	var zipTypes = new[] { "postal_code" };
	var location = businessResults.Element("geometry").Element("location");
	var reviews = businessResults.Elements("review").Select(r => new GooglePlacesReview
	{
		ReviewDate = FromUnixTime(r.Element("time").Value.TryParseValue<Int64>()),
		ReviewText = r.Element("text").Value,
		AuthorName = r.Element("author_name").Value,
		Rating = r.Element("rating").Value.TryParseValue<Decimal>(),
		Language = r.Element("language").Value
	});
	var openingHours = businessResults.Element("opening_hours");
			
	return new GooglePlacesResult 
	{
		Name = businessResults.Element("name").Value,
		Address = street.Remove(street.LastIndexOf(",")),
		PhoneNumber = businessResults.Element("formatted_phone_number").Value,
		City = addressComponents.FirstOrDefault(e => cityTypes.Any(s => s == e.Element("type").Value)).Element("long_name").Value,
		State = addressComponents.FirstOrDefault(e => stateTypes.Any(s => s == e.Element("type").Value)).Element("long_name").Value,
		Country = addressComponents.FirstOrDefault(e => countryTypes.Any(s => s == e.Element("type").Value)).Element("long_name").Value,
		Zip = addressComponents.FirstOrDefault(e => zipTypes.Any(s => s == e.Element("type").Value)).Element("long_name").Value,
		Latitude = location.Element("lat").Value.TryParseValue<Decimal>(),
		Longitude = location.Element("lng").Value.TryParseValue<Decimal>(),
		Rating = businessResults.Element("rating").Value.TryParseValue<Decimal>(),
		Url = businessResults.Element("url").Value,
		InternationalPhoneNumber = businessResults.Element("international_phone_number").Value,
		Reviews = reviews,
		OpenNow = openingHours.Element("open_now").Value.TryParseValue<bool>(),
		OpenHours = openingHours.Elements("weekday_text").Select(e => e.Value),
		UtcOffset = businessResults.Element("utc_offset").Value.TryParseValue<Int32>(),
		UserRatingsTotal = businessResults.Element("user_ratings_total").Value.TryParseValue<Int32>()
	};
}

Some things to talk about. Google places returns a collection of address_component nodes. Each of these has a type that defines what it is. The definitions can be found here. Using Linq we’re able to simplify the data retrieval process.

Wrapping Up

So hopefully this has been informative, if you’ve enjoyed reading please leave a comment below or see if I’ve made any mistakes or a better way of doing this I would love to hear it, thanks!