• ホーム
  • C#
  • C#でスタックを使って逆ポーランド記法の計算をしてみた

C#でスタックを使って逆ポーランド記法の計算をしてみた

逆ポーランド記法で書かれた数式を、スタックを使って計算してみました。中置記法を逆ポーランド記法に変換したのは、数式を文字列で入力して計算したかったからです。

目次

  1. 計算の手順
  2. 試してみた
    1. ビュー
    2. コード
    3. 動かしてみた

計算の手順

  1. 逆ポーランド記法の数式を、要素毎にスタックに積みます。（数式の先頭の要素が一番上になるような並びのスタックにします。）

  2. 計算用の空のスタックを作ります。

  3. 数式のスタックからPopして、数値の場合は計算用のスタックにPushします。

  4. 四則演算の演算子の場合は、計算用のスタックから2つPopして計算し、計算結果を計算用のスタックにPushします。

  5. 三角関数の場合は、計算用のスタックから1つPopして計算し、計算結果を計算用スタックにPushします。

  6. 数式のスタックが空になったら、計算用のスタックのオブジェクトは１つになっているはず。それが計算結果です。

逆ポーランド記法とか、スタックへの数値の出し入れで計算するとか、最初に考えた人はすごいですよねえ。

試してみた

極めて単純ですが、作ってみました。 数値は数字1文字、演算子は+と-だけ、三角関数は正弦だけでsと入力する、という縛りで入力した逆ポーランド記法の数式の計算結果を計算してみます。

ビュー

<Window x:Class="trial_calc_rpn.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:trial_calc_rpn"
        mc:Ignorable="d"
        Title="MainWindow" Height="200" Width="300">
    <Grid>
        <Grid.RowDefinitions>
            <RowDefinition Height="40" />
            <RowDefinition Height="40" />
            <RowDefinition Height="1*" />
        </Grid.RowDefinitions>
        <TextBox Name="textboxInput" Grid.Row="0" Margin="5" />
        <Button Name="button" Content="計算" Grid.Row="1" Margin="5" Click="button_Click" />
        <TextBlock Name="textblockResult" Grid.Row="2" Margin="5" />
    </Grid>
</Window>

入力用のテキストボックスと、ボタンと、出力用のテキストブロックを並べただけ。

コード

using System;
using System.Collections.Generic;
using System.Windows;

namespace trial_calc_rpn
{
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
        }

        private void button_Click(object sender, RoutedEventArgs e)
        {
            Stack<string> inputRPN = new Stack<string>(); // 元の数式を入れるスタック
            Stack<double> calcResult = new Stack<double>(); // 計算結果を入れるスタック

            foreach (char s in textboxInput.Text) // テキストボックスのテキストをスタックに積む
            {
                inputRPN.Push(s.ToString());
            }
            Stack<string> reversedRPN = new Stack<string>();
            while (inputRPN.Count > 0) // 式の積み方を逆順にしたスタックを作る
            {
                reversedRPN.Push(inputRPN.Pop());
            }

            while (reversedRPN.Count > 0)
            {
                string token = reversedRPN.Pop();
                double token_double;
                if (double.TryParse(token, out token_double)) // 数値の場合
                {
                    calcResult.Push(token_double);
                }
                else
                {
                    if (token == "+") // +演算子の場合
                    {
                        double tempA = calcResult.Pop();
                        double tempB = calcResult.Pop();
                        calcResult.Push(tempA + tempB);
                    }
                    else
                    {
                        if (token == "-") // -演算子の場合
                        {
                            double tempA = calcResult.Pop();
                            double tempB = 0.0;
                            if (calcResult.Count > 0)
                            {
                                tempB = calcResult.Pop();
                            }
                            calcResult.Push(tempB - tempA);
                        }
                        else
                        {
                            if (token == "s") // 三角関数（正弦）の場合
                            {
                                double tempA = calcResult.Pop();
                                calcResult.Push(Math.Sin(tempA));
                            }
                        }
                    }
                }

            }
            textblockResult.Text = calcResult.Peek().ToString(); // 計算結果を表示
        }
    }
}

数式を最初の文字からスタックにPushすると計算に使えないので、一度作ったスタックを逆順に入れ替えています。たぶんreverseメソッドあたりを使うとか、文字列を後ろから読むとかするのがスマートでしょう。 上記のコードですとifのネストが滅茶苦茶深くなります。適度にswitchするなどしましょう。

動かしてみた

実行するとこうなります。 image0

逆ポーランド記法
123+-3s+

中置記法
1-(2+3)+sin(3) = -3.858879992

中置記法の方はExcelで計算しました。 合ってるっぽいですね。

Previous: C#で数式を中置記法から後置記法（逆ポーランド記法）に変換してみた（三角関数編）   Next: C#でDataAdapterを使ってAccessのデータベースを読み書きしてみた（OleDb編）

公開日

広告

C#カテゴリの投稿