Page 1 of 1

[Silverlight C#] Reverse Polish Notation Calculator A Reverse Polish Notation (RPN) calculator application in Silverlight.

#1 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4438
  • View blog
  • Posts: 7,719
  • Joined: 08-June 10

Posted 26 November 2010 - 12:58 PM

Have any of you ever used a Reverse Polish Notation calculator? I did in high school. It was easily the best calculator ever (the HP=32SII). RPN is great, because you don't have to use parenthesis. The stack and the order in which you key the operators maintains order of operations.

Today, I'll walk you through creating one. Note this tutorial is technically for Silverlight, but except for the marked sections, it can be applied wholesale to WinForms or WPF. Most if this is simple stack logic, and that exists on all .NET platforms.

Note: I'm assuming you are familiar with stack operations. If not, please visit the linked MSDN page for information.

Before we start programming, you have to understand postfix notation. Consider the following:

5 6 +


This is a postfix expression, equating to 11. The logical steps to evaluate it are:
  • Push(5)
  • Push(6)
  • var b = Pop()
  • var a = Pop()
  • Push(a + b)
  • Peek()


Consider a more complicated expression:

10 4 6 + 9 * -


This evaluates to -80. It is the equivelant of 10 - (( 4 + 6 ) * 9) in Infix (standard) notation. The same basic steps are followed here.
  • Push(10)
  • Push(4)
  • Push(6)
  • var b = Pop()
  • var a = Pop()
  • Push(a + b)
  • Push(9)
  • var b = Pop()
  • var a = Pop()
  • Push(a * b)
  • var b = Pop()
  • var a = Pop()
  • Push(a - b)
  • Peek()


The basic logic is to push numbers onto the stack until you encounter an operator. At that point, you pop the top two off the stack, evaluate them with the operator, and push the result back onto the stack. After evaluation, Peek for display.

In RPN calculator terms, there is an ENTER button to push a value onto the stack. Also, to save time, if you're currently entering a number, pushing an operator button will also push the number onto the stack.

So for 5 6 + 3 *, we'd push:
5 [ENTER] 6 [+] 3 [*].

For 1 6 2 / 3 4 / * + (which is the equivalent of 1 + (( 6 / 2 ) * ( 3 / 4 )), you'd push:
1 [ENTER] 6 [ENTER] 2 [/] 3 [ENTER] 4 [/] [*] [+]

On a standard calculator, you'd have to use the Memory function to do this with the proper order of operation. With a graphing calculator, you'd have to use parenthesis. But since you can keep state in the stack, you don't have to worry about any of that with an RPN calc.

So, without further ado, lets get into the code.

Setup

We'll obviously need a stack:

private Stack<double> stack;


We'll also need some Dictionaries to relate keyboard keys with strings, since we're not trusting the users to enter numbers by themselves:

private Dictionary<Key, string> opKeys = new Dictionary<Key, string>();
private Dictionary<Key, string> numKeys = new Dictionary<Key, string>();

private void InitializeDictionaries()
{
    opKeys.Add(Key.C, "C");
    opKeys.Add(Key.Back, "B");
    opKeys.Add(Key.Add, "+");
    opKeys.Add(Key.Subtract, "-");
    opKeys.Add(Key.Multiply, "*");
    opKeys.Add(Key.Divide, "/");
    opKeys.Add(Key.Enter, "E");
    opKeys.Add(Key.Decimal, ".");

    numKeys.Add(Key.D0, "0");
    numKeys.Add(Key.D1, "1");
    numKeys.Add(Key.D2, "2");
    numKeys.Add(Key.D3, "3");
    numKeys.Add(Key.D4, "4");
    numKeys.Add(Key.D5, "5");
    numKeys.Add(Key.D6, "6");
    numKeys.Add(Key.D7, "7");
    numKeys.Add(Key.D8, "8");
    numKeys.Add(Key.D9, "9");
    numKeys.Add(Key.NumPad0,  "0");
    numKeys.Add(Key.NumPad1,  "1");
    numKeys.Add(Key.NumPad2,  "2");
    numKeys.Add(Key.NumPad3,  "3");
    numKeys.Add(Key.NumPad4,  "4");
    numKeys.Add(Key.NumPad5,  "5");
    numKeys.Add(Key.NumPad6,  "6");
    numKeys.Add(Key.NumPad7,  "7");
    numKeys.Add(Key.NumPad8,  "8");
    numKeys.Add(Key.NumPad9,  "9");
}


Now, we're going to use Lambda methods for the operators. This makes things quite simple. If you're not familiar with what's going on here, I have a tutorial on Lambdas that you're welcome to read. They're basically a shorthand way to write anonymous methods. And the Func object is a way to store these methods as objects. We're going to make a Dictionary of Funcs keyed by strings:

private Dictionary<string, Func<double, double, double>> op =
    new Dictionary<string, Func<double, double, double>>();

private void InitializeOp()
{
    op.Add("+", (a, B) => a + B);
    op.Add("-", (a, B) => a - B);
    op.Add("*", (a, B) => a * B);
    op.Add("/", (a, B) => a / B);
}


If this seems strange to you, here's an example of how we would invoke this.

This doesn't go in the project. This is just an example of using Funcs in a dictionary.
double a = 5, b = 6;
double result = op["+"](5, 6);


Now we've stored methods in a dictionary, and depending on which operator we pass, the proper one will be invoked. This is quite useful, because it allows us to skip a switch or if else if statement.

Also, two more bools we'll need to keep track of state:

private bool clearOnNext, errorState;


clearOnNext lets us know if the next number we push will start a new number or append to the current one. errorState is a simple bool that lets us know if we're currently reporting an error to the user (like Div By Zero or Out of Stack).

Silverlight Specific: XAML MARKUP (display code)

Here's the XAML markup we're using. This could be replicated by WinForms, but I prefer to work with Silverlight/WPF whenever I can.

I've put it in a spoiler tag, because it's a little on the long side.
Spoiler


One neat thing I did was to make a new style for a Button. I copied the Button's default template from the MSDN, but the one small change I made was putting the <ContentPresenter> inside a <Viewbox>. The Viewbox is a neat control that will stretch and scale a single child to fill all available space. Without it, the buttons can scale to fit, but the text inside would remain the same size. With it, the text scales to fill the button. Here's the template. It's also in a spoiler:

Spoiler


Non-Silverlight Specific

If you're not doing this in Silverlight, the important thing to note for the rest of this tutorial is that I'm assuming you created a Read Only TextBox named "displayTextBox". You can name it whatever you like, just make sure to change it in the code as well. Another thing I've assumed is that you've created all your buttons, and set their Tag properties to their numeral or operator value. Also, they all should call the same handler for their Click event: "Button_Click". One more thing, I've attached an event handler to the KeyUp event of the displayTextBox.

Here's a property we'll be using for convenience sake:

private double current
{
    get
    {
        if (displayTextBox.Text == string.Empty)
            displayTextBox.Text = "0";
        return double.Parse(displayTextBox.Text);
    }
}


This simply parses what's in the TextBox as a double.

Initialization

Here's how our constructor will look:

public MainPage()
{
    InitializeComponent();
    InitializeDictionaries();
    InitializeOp();
    stack = new Stack<double>();
    this.Loaded += (s, ea) =>
    {
        if (!App.Current.IsRunningOutOfBrowser)
            System.Windows.Browser.HtmlPage.Plugin.Focus();
        displayTextBox.Focus();
    };
    clearOnNext = false;
    errorState = false;
}


There's a lambda in here too. It's just a quick event handler to set the focus onto the Display TextBox when the program loads. Since for some reason, the Silverlight app doesn't focus itself when it starts, I've added a line to tell the browser to first focus the SL app first.

Methods

The simplest method we need to add has to handle input. We'll call this one from handlers.

private void ProcessInput(string input)
{
    if (clearOnNext)
    {
        displayTextBox.Text = string.Empty;
        clearOnNext = false;
        errorState = false;
    }
    displayTextBox.Text += input;
}


It checks to see if we're starting a new number. If so, it clears it and resets the state, otherwise, it just appends text.

We'll also need a method to process special characters like "Clear", "Enter", "Backspace", and "Decimal" as well as the operators

private void ProcessSpecial(string input)
{
    switch (input)
    {
        case "C":
            if (displayTextBox.Text.Length > 0)
                displayTextBox.Text = string.Empty;
            else
            {
                stack.Clear();
                RefreshDepthText();
            }
            clearOnNext = false;
            break;
        case "B":
            if (!clearOnNext && displayTextBox.Text.Length > 0)
                displayTextBox.Text = displayTextBox.Text.Substring(0, displayTextBox.Text.Length - 1);
            break;
        case ".":
            if (!displayTextBox.Text.Contains("."))
            {
                if (displayTextBox.Text.Length < 1 || errorState)
                    ProcessInput("0.");
                else
                    ProcessInput(".");
            }
            break;
        case "E":
            Enter();
            break;
        case "+":
        case "-":
        case "*":
        case "/":
            DoOp(input);
            break;
    }
}


This one walks through the possibilities in a switch statement and takes the appropriate action. At this point, some of the methods defined here are undeclared. We'll soon remedy this. I'll also explain each case.

Case "C" is clear. First click, it clears the display. Second (or first if the display is already clear) clears the stack.

Case "B" is backspace. Substring if there's room to.

Case "." handles the decimal. We only allow one of those, and for visual's sake, add a 0 in front if it's the first button clicked.

Case "E" is enter. We'll write that method soon.

The remaining cases are operators. We'll also look at that method soon.

Calculator Logic methods

Here's the Enter method now:

private void Enter()
{
    if (!errorState)
    {
        stack.Push(current);
        RefreshDepthText();
        clearOnNext = true;
    }
}


It's quite simple. We don't want to try to push an error message on the stack, so we check for that first. If there's no error, we push the current value onto the stack, and refresh the Depth Text Display (this just shows a count of how much is on the stack). Also, we set clearOnNext to true, since we'll be starting a new number.


Here's the method where we actually do an operation:

private void DoOp(string input)
{
    if (!clearOnNext)
    {
        stack.Push(current);
    }
    if (stack.Count < 2)
    {
        errorState = true;
        clearOnNext = true;
        displayTextBox.Text = "OUT OF STACK";
        return;
    }
    double b = stack.Pop();
    double a = stack.Pop();
	stack.Push(op[input](a, B));
	double res = stack.Peek();
	if (res == double.NegativeInfinity || res == double.PositiveInfinity || res == double.NaN)
	{
        stack.Clear();
        RefreshDepthText();
        errorState = true;
        clearOnNext = true;
        displayTextBox.Text = "DIV BY ZERO";
		return;
	}
	displayTextBox.Text = stack.Peek().ToString();
	RefreshDepthText();
	clearOnNext = true;
}


The first if statement checks to see if we've been entering a new number. Remember, the way an RPN calc works is that if you're entering a number, an operator key will push that number for you. Next, we check to see if we can pop enough values to proceed. If you try to do an operation that there's not enough numbers for, you'll "run out of stack." Once we know we can, we pop both values, b first (this only matters for subtraction and division). Now we perform the actual operation. My first thought was that we could use a Try/Catch to check for Div By Zero, but apparently that results in double.PositiveInfinity. The string "Infinity" is also a valid parsable double, by the way. So I'm just checking the result now.

Anyway, if everything was successful, Peek the value into the textbox, and move on.

Now, a keen observer would note that while we're set up to handle the calculator logic now, we have no way of actually entering numbers or operators. Have no fear, that's the next section.

Input logic

We've set up event handlers for the KeyUp on the readonly textbox as well as handling the Click event for each button. Here's the code for those event handlers:

private void Button_Click(object sender, RoutedEventArgs e)
{
    string value = (sender as Button).Tag as string;
    if (numKeys.ContainsValue(value))
        ProcessInput(value);
    else
        ProcessSpecial(value);
    displayTextBox.Focus();
}

private void DisplayTextBox_KeyUp(object sender, KeyEventArgs e)
{
    if (opKeys.ContainsKey(e.Key))
        ProcessSpecial(opKeys[e.Key]);
    else if (numKeys.ContainsKey(e.Key))
        ProcessInput(numKeys[e.Key].ToString());
    else return;
}


Miscellaneous methods

These don't hold much importance, just necessary for little things:

private void RefreshDepthText()
{
    stackDepthTextBlock.Text = stack.Count.ToString();
}

private void copyButton_Click(object sender, RoutedEventArgs e)
{
    Clipboard.SetText(current.ToString());
}

private void pasteButton_Click(object sender, RoutedEventArgs e)
{
    if (!Clipboard.ContainsText())
        return;
    string s = Clipboard.GetText();
    double x;
    if (double.TryParse(s, out  x))
        displayTextBox.Text = s;
}


And that's that. If you've followed the instructions properly, you'll have a calculator like this one:

Posted Image

Coming up next: ported to WP7!

Cross posted from my blog.

This post has been edited by insertAlias: 28 November 2010 - 05:26 PM


Is This A Good Question/Topic? 2
  • +

Page 1 of 1