C#で数式を中置記法から後置記法（逆ポーランド記法）に変換してみた

数式を示す文字列を、逆ポーランド記法に変換してみました。数値は自然数のみ、演算は加減乗除のみに対応したものですが、追々応用していけばよろしいかと思ったわけです。手法としては、スタックを使った変換です。 逆ポーランド記法についてはウィキペディアを参照してください。

目次

  1. 逆ポーランド記法に変換するアルゴリズム
  2. 試してみた
    1. ビュー
    2. コード
    3. 動かしてみた

逆ポーランド記法に変換するアルゴリズム

数式を逆ポーランド記法に変換 や 逆ポーランド記法への変換２ を参考にさせていただきました。 参考させていただいたサイトのフローチャートでちょっと詰まりました。 トークンが演算子だった場合の処理について「スタックの最上段の演算子よりトークンの演算子の優先順位が低い」がyesのときに「スタックからポップ　それをバッファへ」と書いてあります。なんとなく、演算子の優先順位は「乗算と除算」＞「加算と減算」という意識で読んでしまったので、乗算と除算が続けて行われる式の場合に乗算と除算の順番が入れ替わってしまいました。（サイトの計算例の結果が14+37+5/*になってしまった。） サイトの制作者様には当たり前だったのかもしれないのですが、乗算と除算の場合は先に計算される方が優先順位が高いと考えれば良いわけですね。（最終的には14+37+*5/が得られました。）

試してみた

数式を逆ポーランド記法に変換するプログラムを作ってみました。

ビュー

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

<Window x:Class="trial_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_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="textbox" Grid.Row="0" Margin="5" />
        <Button Name="button" Content="変換" Grid.Row="1" Margin="5" Click="button_Click" />
        <TextBlock Name="textblock" Grid.Row="2" Margin="5" />
    </Grid>
</Window>

コード

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

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

        private void button_Click(object sender, RoutedEventArgs e)
        {
            Stack<char> buffer = new Stack<char>(); // バッファ
            Stack<char> st = new Stack<char>(); // 作業用のスタック
            textblock.Text = string.Empty;

            foreach(char token in textbox.Text)
            {
                switch (token)
                {
                    case '(':
                        st.Push(token);
                        break;
                    case ')':
                        while (st.Count>0)
                        {
                            char t = st.Pop();
                            if (t == '(')
                            {
                                break;
                            }else
                            {
                                buffer.Push(t);
                            }
                        }
                        break;
                    case '*':
                    case '/':
                        while (st.Count > 0)
                        {
                            if (st.Peek() == '*' || st.Peek() == '/')
                            {
                                buffer.Push(st.Pop());
                            }else
                            {
                                break;
                            }
                        }
                        st.Push(token);
                        break;
                    case '+':
                    case '-':
                        while (st.Count > 0)
                        {
                            if (st.Peek() == '*' || st.Peek() == '/' || st.Peek()=='+'||st.Peek()=='-')
                            {
                                buffer.Push(st.Pop());
                            }else
                            {
                                break;
                            }
                        }
                        st.Push(token);
                        break;
                    default: // 数字の場合
                        buffer.Push(token);
                        break;
                }
            }
            while (st.Count > 0) // スタックが空になるまでpopしてバッファへ移動
            {
                buffer.Push(st.Pop());
            }
            string r = new String(buffer.Reverse().ToArray<char>()); // スタックの順番を逆順にして文字列に変換
            textblock.Text = textblock.Text + r + "\r\n";
        }
    }
}

括弧と演算子以外は全て数字とみなすという、強引なコードです。このままでは汎用性は低そう。

動かしてみた

参考サイトの数式を入れてみました。 image0 以下、いくつか試してみました。

中置法 → 逆ポーランド記法
(1+4)*(3+7)/5 → 14+37+*5/
a+b → ab+
a+(b*c) → abc*+
(a+b)*c → ab+c*
a*b+c*d+e*f → ab*cd*+ef*+
((a+b)*(c+d)+e)*f → ab+cd+*e+f*
Previous: C#で画像をグレースケールや半透明に変換するアプリを作ってみた   Next: C#で選択（switch-case編）

公開日

広告

C#で作ってみたカテゴリの投稿