65.9K
CodeProject is changing. Read more.
Home

Parsing a postfix expression in C#, my naive approach

starIconstarIconstarIconstarIconstarIcon

5.00/5 (7 votes)

Nov 22, 2010

CPOL
viewsIcon

21596

There was a request about in Q&A. The question was deleted, anyway I think the subject may be interesting.

Parsing a postfix expression is indeed really simple, the recipe is
  • Parse the input string for either a number or an operator (here I assume just binary operators).
  • If a number is found put it onto the stack.
  • If an operator is found pop the two numbers from top of the stack, perform the binary operation and put the result again onto the stack.
  • At the end the stack must contain just one element, the result
The following code sample does in naive, simple and rough way (hey, I'm new to C#...), it's job:
using System;
using System.Text.RegularExpressions;
using System.Collections.Generic;

namespace Postfix
{
	class Parser
	{
		public delegate int BinOp(int a, int b);
		static int add(int a, int b) { return a + b;}
		static int sub(int a, int b) { return a - b; }
		static int mul(int a, int b) { return a * b; }
		static int div(int a, int b) { return a / b; }

		static int parseExp(string s)
		{
			Dictionary<string, BinOp> oper = new Dictionary<string, BinOp>();	
			List<int> stack =new List<int>();

			oper["+"] = add;
			oper["-"] = sub;
			oper["*"] = mul;
			oper["/"] = div;

			Regex rxnum = new Regex(@"\G\s*-?([0-9]+)\s+");
			Regex rxop = new Regex(@"\G(\+|\-|\*|\/)");
			int start = 0;
			do
			{
				Match m = rxnum.Match(s, start);
				if (m.Success)
				{
					stack.Add(Int32.Parse(m.ToString()));
				}
				else
				{
					m = rxop.Match(s, start);
					if (m.Success)
					{
						int c = stack.Count;
						if (c < 2) throw new Exception("Invalid expression: out of stack.");
						stack[c - 2] = oper[m.ToString()](stack[c - 2], stack[c - 1]);
						stack.RemoveAt(c - 1);
					}
					else break;
				}
				start = start + m.Length;
			} while (true);

			if (stack.Count != 1) throw new Exception("Invalid expression: more than one result on stack.");
			if (start != s.Length) throw new Exception("Invalid expression: unrecognized token.");

			return stack[0];
		}

		static void Main()
		{
			string exp = "23 5 - 12 *";
			Console.WriteLine("expression '{0}' result is '{1}'", exp,  Parser.parseExp(exp));
		}
	}
}
:)