Click here to Skip to main content
Click here to Skip to main content

Tagged as

Parsing a postfix expression in C#, my naive approach

, 22 Nov 2010 CPOL
Rate this:
Please Sign up or sign in to vote.
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));
		}
	}
}
 

Smile | :)

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

CPallini
Software Developer (Senior) AEM S.p.A.
Italy Italy




Debugging? Klingons do not debug. Our software does not coddle the weak. Bugs are good for building character in the user.
-- The Klingon programmer


Beelzebub for his friends [^].



Follow on   LinkedIn

Comments and Discussions

 
GeneralThank you, Raja. PinmvpCPallini1-Jan-11 7:37 
Thank you, Raja.
GeneralReason for my vote of 5 Good one dude Pinmvpthatraja1-Jan-11 7:30 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.141015.1 | Last Updated 22 Nov 2010
Article Copyright 2010 by CPallini
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid