AtCoder Problems のパクリアプリ CF Problems を作りました

概要

AtCoder Problems を模倣して CF Problems という Web Application を作りました.

はじめに

AtCoder ProblemsCodeforces 版みたいな Web Application があったら良いなと思っていたのですが, これまでのところ私の観測する範囲では存在していませんでした. そして, ちょうど Web フロントエンドの勉強をしたいということもあり良い機会だと思って作りました. 下記に示すリンクから作ったものを見ることが出来ます.

cf.kira924age.com

CodeforcesCodeforces API という API を公開しているので今回はこれを利用しました. 開発の際は AtCoder Problemsyukicoder problems のコードを参考にさせてもらいました. 宇宙ツイッタラーX (@kenkoooo) さん, iiljj さん, その他のコントリビューターの皆さんに感謝してます.

CF Problems とは?

CF ProblemsCodeforces API を利用して Codeforces の問題およびユーザー情報を本家とは違う形で表示するフロントエンドツールです. AtCoder Problems っぽいものを目指して作りましたが, 実装が面倒あるいは Codeforces API のみでは不可能だった機能を省きました.

まず. ページが TableUser の2種類しかありません. List は面倒だったので省きました. (今後やる気があれば実装するかもしれません)

それぞれのページの外観は以下の画像が示す通りです.

  • Table ページの外観

f:id:kira000:20210305205027p:plain
Table ページの外観

  • User ページの外観

f:id:kira000:20210305205206p:plain
User ページの外観

AtCoder Problems に寄せた外観であることが確認できます.

既知の問題点

CF Problems には現時点で把握しているだけでも以下のような問題点があります.

  • 本来表示されて欲しい問題が Table ページに表示されないことがある.

例えば直近では Codeforces Round #700 (Div. 2) のC問題以降が Table で表示されていません. これは Codeforces API の仕様なのでフロントエンド側で対処するのは難しそうです. なので当分あるいは永遠に改善されないと思います.

  • Dark Theme で Table を Chrome 系のブラウザで表示すると右に謎の白い線が入る

以下の画像に示すとおり謎の白い線が Table に右側に表示されています. CSS を色々いじったのですが消えてくれないです. ちなみに FireFox ではなぜか表示されません. 意味不明です.

f:id:kira000:20210305213750p:plain
謎の白い線

  • コードが雑

これは機能的な問題ではないのですが, コードがとても雑です. Web フロントエンド初心者が雑に書いたものなのでそれはそうです. 具体的に言うと, TypeScript の型定義をサボって any を多用した, エラーハンドリングをサボった, などがあります.

コードが雑なので把握していないバグが潜んでいる可能性は非常に高いです.

汚いコードは下記の GitHubリポジトリから見ることが出来ます.

github.com

使用したツール

最後にアプリケーションを作る上で利用したツールを書いておきます.

GNOMEで時刻表示形式を変更する

概要

GNOMEUnixライクなOSで動作するオープンソースのデスクトップ環境です. 現在, UbuntuCentOS などの多くのLinuxディストリビューションで標準のデスクトップ環境として採用されています.

今回はGNOMEにおいて時刻表示形式をどのように変更するかを調べました.

環境

以下のような環境で検証しました.

$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.4 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic
$ gnome-shell --version
GNOME Shell 3.28.4

設定 (Settings)

設定 (Settings) からは表示形式を 24時制/12時制 のいずれかに変更することができます.

この変更画面にたどり着くのも少し面倒なので手順を述べます.

  • 設定 (Settings) を開く. (左上の アクティビティ (Activity) ボタンを押して, Settings と入力すると開けます)
  • サイドバーの一番下の詳細 (Details) ボタンを押す.
  • サイドバーの日付と時刻 (Date & Time) を押す.

Tweaks

GNOMEのUIのカスタマイズをGUIから行える Tweaks というツールがあります.

下記のコマンドでインストールできます.

$ sudo apt install gnome-tweaks

Tweaks のトップバー (topbar) という項目から日付や秒を表示するかどうかを選択できます.

Clock Override

Clock Override というGNOME拡張機能により, ステータスバー(トップバー)の時刻表示形式を変更することができます.

インストールはブラウザ経由で行う方法とUbuntuソフトウェアセンターから方法があります.

Ubuntu ソフトウェアセンターまたは https://extensions.gnome.org の検索バーに Clock Override と入力して適当にボタンを押せばインストールできます.

拡張機能は Tweaks の拡張機能/Extension という項目から設定できます.

Clock Override を使うことで, トップバーに表示される時計の時刻表示形式は自由に変更できます.

Datetime Format

Datetime Format というGNOME拡張機能により, トップバーおよび日付メニューの時刻表示形式を変更することができます.

文字コードに日本語を含むものを指定すると, 設定自体はできるのですが, それ以降この拡張機能の設定をしようとすると以下のようなエラーが出ます.

Error: Failed to convert locale string to UTF8: 変換する入力に無効なバイトの並びがあります

Stack trace:
  dateTimeFormat@/home/kira/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com/Utilities.js:15:20
  create/updatePreview@/home/kira/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com/FormatTarget.js:49:25
  create@/home/kira/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com/FormatTarget.js:55:2
  buildPrefsWidget/<@/home/kira/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com/prefs.js:136:61
  buildPrefsWidget@/home/kira/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com/prefs.js:136:2
  _selectExtension@resource:///org/gnome/shell/extensionPrefs/main.js:91:22
  wrapper@resource:///org/gnome/gjs/modules/_legacy.js:82:22
  _onCommandLine@resource:///org/gnome/shell/extensionPrefs/main.js:243:17
  wrapper@resource:///org/gnome/gjs/modules/_legacy.js:82:22
  main@resource:///org/gnome/shell/extensionPrefs/main.js:397:5
  @<main>:1:43

どうやら Unicode をサポートしていないようです. Github に issue が立ってました.

GSettings

GUIによる Datetime Format の設定ができなくなったので, GSettings を使って Datetime Format の値の設定をしてみます.

GNOMEにおいて日付の表示形式を含むユーザの設定情報は dconf という設定システムにより管理されています.

GSettingsdconf のフロントツールで, 設定を行うためのAPI群です.

gsettings コマンドにより, ユーザ設定の編集を行うことができます. man gsettigns と言うコマンドを叩くとマニュアルが表示されます.

以下のコマンドで Datetime Format の key をリスト表示させてみます.

$ gsettings --schemadir ~/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com list-keys org.gnome.shell.extensions.datetime-format
datemenuday-format
statusbar-format
statusbar-toggle
datemenudate-toggle
datemenudate-format
datemenuday-toggle

statusbar-format の値を変更することでステータスバー (トップバー) の時刻表示形式を変えてみます. 日付の書式文字列は man date とするとマニュアルを参照できます.

以下のコマンドで, statusbar-format の値を %m月%d日(%a) %H:%M に変更できます.

$ gsettings --schemadir ~/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com set org.gnome.shell.extensions.datetime-format statusbar-format "%m月%d日(%a) %H:%M"

以下のコマンドで, datemenuday-format の値を %H:%M:%S に変更できます.

$ gsettings --schemadir ~/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com set org.gnome.shell.extensions.datetime-format datemenuday-format "%H:%M:%S"

以下のコマンドで, datemenudate-format の値を %Y年%m月%d日(%a) に変更できます.

$ gsettings --schemadir ~/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com set org.gnome.shell.extensions.datetime-format datemenudate-format "%Y年%m月%d日(%a)"

これらの設定により時刻表示部分は以下のような外観となりました. カレンダーの月の値の表示の下部が少し隠れているのが気になりますが概ね良さそうです.

f:id:kira000:20200629073956p:plain

参考文献

転倒数 アルゴリズム

転倒数 (inversion number) とは?

数列 a = {a_0, a_1, a_2 ... a_n-1 } が与えられたとき,

i < j かつ a_i > a_j を満たす (i, j) の組の個数を転倒数または反転数という.

たとえば a = {3, 1, 5, 4, 2} のとき,

i < j かつ a_i > a_j となっている組は,

(3, 1), (3, 2), (5, 4), (5, 2), (4, 2) の 5組であるから転倒数は 5 となる. (添字ではなく要素の組を列挙した)

転倒数は下記のようなバブルソートを行った際の交換回数と等しくなることが知られている. 一回の交換で反転数は1減少し, ソートが完了すると反転数は0となるのでそれはそう.

#!/usr/bin/env python3

def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt

直感的には転倒数は昇順ソートされた状態を正しい並びとしたとき, 正しくない並びとなっている組の数と考えることができる.

転倒数を愚直な実装で求めると時間計算量は  O(n^{2}) となるが以下に示すように  O(n \log{n})アルゴリズムが存在する.

Fenwick Tree(Binary Indexed Tree)を用いる方法

i < j かつ a_i > a_j を満たす要素を数えるには以下の 2 つの方法が考えられる.

  • i についてループを回し i < j かつ a_i > a_j となるものを数える.

  • j についてループを回し i < j かつ a_i > a_j となるものを数える.

どちらもほぼ同じように見えるが, 後者のように考えないとうまくいかない.

後者の方法で i < j かつ a_i > a_j となるものを数えるとき Fenwick Tree を使うと各 j について  O(\log{n}) で求めることができる.

Fenwick Tree は区間の和の計算, 要素の値の更新がそれぞれ  O(\log{n}) でできるデータ構造.

  • C++ による Fenwick Tree の実装例
struct fenwick_tree {
    typedef int T;
    T n;
    vector<T> bit;

    // 各要素の初期値は 0
    fenwick_tree(T num) : bit(num+1, 0) { n = num; }

    // a_i += w
    void add(T i, T w) {
        for (T x = i; x <= n; x += x & -x) {
            bit[x] += w;
        }
    }
    // [1, i] の和を計算.
    T sum(T i) {
        T ret = 0;
        for (T x = i; x > 0; x -= x & -x) {
            ret += bit[x];
        }
        return ret;
    }
    // [left+1, right] の和を計算.
    T sum(T left, T right) {
        return sum(right) - sum(left);
    }
};
  • 使い方

    • fenwinck_tree f_tree(n); で size n の tree を作成.
    • f_tree.sum(x)区間 [1, x] の和を求める.
    • f_tree.sum(l, r)区間 [l+1, r] の和を求める.

    • f_tree.add(i, w) で 0-based-index で i 番目の要素に w を足す.

Fenwick Tree は最初 a = {a_0, a_1, a_2 ... a_n-1} の数列があり, 各要素の初期値は 0 となっている.

j = 0 から n-1 までループを回し. 以下のような処理をすることで転倒数を求めることができる.

fenwinck_tree f_tree(n);

for (int j = 0; j < n; j++) {
    ans += j - f_tree.sum(a[j]);
    f_tree.add(a[j], 1);
}

fenwick tree の i 番目の値が x であるとき, 値が i である要素が x 個あるものとみなす. すると sum(a[j]) が返す値は i < j かつ a_i <= a_j の個数となる. なぜなら sum(a[j]); が実行されるとき fenwick tree に追加されている数列の要素は必ず, 現在の j より小さいときに追加されたものであり(i < j を満たす), sum(a[j]) は区間[1, a[j]] の和であるから.

数えたいのは i < j かつ a_i > a_j であるから, 現在見ている数列の要素の個数である j から sum(a[j]) を減算した値を足せば良い.

注意点としては size n の tree を作成する際の n の値は数列の最大値より大きなものを設定する必要があるという点と, 数列の要素に0以下のものがあると要素の追加ができないので下駄を履かせる必要があるという点である.

分割統治法を使う方法

以下のようなコードでマージソートを行いながら転倒数を求めることもできる. (引数として渡した配列はソートされてしまう破壊的な関数である点に注意!!!)

long long merge_cnt(vector<long long> &a) {
  int n = a.size();

  if (n <= 1) {
    return 0;
  }

  long long cnt = 0;

  vector<long long> b(a.begin(), a.begin() + n / 2);
  vector<long long> c(a.begin() + n / 2, a.end());

  cnt += merge_cnt(b);
  cnt += merge_cnt(c);

  int ai = 0, bi = 0, ci = 0;
  // merge の処理
  while (ai < n) {
    if (bi < (int)b.size() && (ci == (int)c.size() || b[bi] <= c[ci])) {
      a[ai++] = b[bi++];
    } else {
      cnt += n / 2 - bi;
      a[ai++] = c[ci++];
    }
  }
  return cnt;
}

与えられた数列を A とし, その数列を B と C に分割(Devide)する.

B, C をそれぞれソート済みとすると, Aの転倒数はBの転倒数とCの転倒数を足し, さらにBとCとの間にまたがって存在する i < j かつ a[i] > a[j] となるような組の数を足したものとなる.

数列 a = {3, 1, 5, 4, 2,} を例として考える. merge_cnt() が実行されると, 数列は以下のように再帰的に分割される.

f:id:kira000:20190223045138p:plain

A = {4, 2}, B = {4}, C = {2} とする. B と C はそれぞれサイズが1なので転倒数は0である.

BとCを merge するとき, cnt がどのように更新されるかを見る.

    while (ai < n) {
        if ( bi < b.size() && (ci == c.size() || b[bi] <= c[ci]) ) {
            a[ai++] = b[bi++];
        } else {
            cnt += n / 2 - bi;
            a[ai++] = c[ci++];
        }
    }

数列 C の要素が Aに merge されるとき (i < j), cnt は更新されている. これは転倒数の定義 (i < j and a[j] < a[i] となる i, j の組の数) を考えれば当然である.

cnt += n/2 - bi;n/2 は数列B のサイズを表している. bi は BのインデックスでBの要素全てがAに代入されると n/2 となる. 数列Cの要素が merge されるとき, 数列 B のうちまだ merge されていない要素の個数を cnt に足している.

merge の処理が済んだ数列はきちんとソートされる.

分割された数列の転倒数を赤で示したのが下図である.

f:id:kira000:20190223050517p:plain

使用例

AOJ: ALDS1-5 D

参考文献

MSYS2にインストールしたImageMagickが正常に動作しない件について

  • まずは下記のようなコマンドで imagemagick をインストールする.
  • 私は 32bit 版を選んだ.
$ pacman -Ss imagemagick
mingw32/mingw-w64-i686-imagemagick 7.0.3.1-1
    An image viewing/manipulation program (mingw-w64)
mingw64/mingw-w64-x86_64-imagemagick 7.0.3.1-1
    An image viewing/manipulation program (mingw-w64)
$ pacman -S mingw-w64-i686-imagemagick

(略)
  • バージョンの確認をしてインストールが正常にされているかを確かめる.
  • このとき msys2.exe で起動すると path が通っていなくてエラーが出るので mingw32.exe を使う. (msys2-launcher を使うことを前提にしてる)
$ convert -version
Version: ImageMagick 7.0.3-1 Q16 i686 2016-10-07 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2016 ImageMagick Studio LLC
License: http://www.imagemagick.org/script/license.php
Features: Cipher DPC HDRI Modules OpenMP
Delegates (built-in): bzlib cairo djvu fftw fontconfig freetype gslib jbig jng jp2 jpeg lcms lqr ltdl lzma openexr pangocairo png ps rsvg tiff webp wmf xml zlib
  • 何かしらのコマンドを使おうとするとエラーが出る.
$ convert test.jpg test.png
convert.exe: no decode delegate for this image format `JPG' @ error/constitute.c/ReadImage/508.
  • 使用可能なフォーマットを表示させようとするも何も表示されない.
$ convert -list format
  • 日本語でググっても解決方法が見つからなかった .
  • 英語でググったらいいのが出てきた (https://github.com/Alexpux/MINGW-packages/issues/1885)
  • coder modulesconfigure のパスが通ってないので次のように bash の設定ファイルを編集しろとのこと.
export MAGICK_HOME="/mingw64/bin"
export MAGICK_CONFIGURE_PATH="/mingw64/etc/ImageMagick-7"
export MAGICK_CODER_MODULE_PATH="/mingw64/lib/ImageMagick-7.0.3/modules-Q16HDRI/coders"
  • 自分の場合は以下のような記述を .bashrc に追加した.
export MAGICK_HOME="/mingw32/bin"
export MAGICK_CONFIGURE_PATH="/mingw32/lib/ImageMagick-7.0.3"
export MAGICK_CODER_MODULE_PATH="/mingw32/lib/ImageMagick-7.0.3/modules-Q16HDRI/coders"
  • 1度閉じて再度起動すると変更が適用される.
$ convert -list format
   Format  Module    Mode  Description
-------------------------------------------------------------------------------
      3FR  DNG       r--   Hasselblad CFV/H3D39II
      AAI* AAI       rw+   AAI Dune image
       AI  PDF       rw-   Adobe Illustrator CS2

(略)
  • ImageMagick をアップデートした際にはその都度 path の値を変更する必要がある.

参考

github.com

github.com

yaritakunai.hatenablog.com

逆ポーランド記法による数式処理

逆ポーランド記法とは

逆ポーランド記法(Reverse Polish Notation: RPN)は、演算子オペランドの後に記述する数式やプログラムの記法の一つです。

例えば、一般的な中間記法で記述された数式 (1+2)*(5+4)逆ポーランド記法では 1 2 + 5 4 + * と記述されます。

逆ポーランド記法では、中間記法で必要とされた括弧が不要であり、また式の計算(評価) の実装が容易であるためコンピュータでの利用に適しています。

演算子を被演算子の後ろに置くことから、後置記法 (Postfix Notation) とも言うらしいです。

逆ポーランド記法で表された数式の評価

実装にはスタックを用います。

先頭から順に記号を読み込み、その記号が演算子以外であればスタックに値を積み、演算子であればスタックから値を2つ取り出して演算結果をスタックに積む、という簡単な操作の繰り返していき、最後にスタックの中に残った値が答えとなります。

AOJ 0087: Strange Mathematical Expression

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0087

試しにこの問題を解いてみましょう。

  • C++による解答例
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <cstdlib>
#include <cctype>
#include <cstdio>

using namespace std;

int main()
{
    string s;
    stack<double> St;
    double a, b;
    while (getline(cin, s)) {
        stringstream ss(s);

        while (ss >> s) {
            if (s == "+") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a+b);
            }
            else if (s == "-") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a-b);
            }
            else if (s == "*") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a*b);
            }
            else if (s == "/") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a/b);
            }
            else {
                St.push(atoi(s.c_str()));
            }
        }
        printf("%.6f\n", St.top());
        St.pop();
    }
    return 0;
}   
# coding: utf-8

def Calculate_RPN(L):
    St = []
    for i in L:
        if i == '+':
            b, a = float(St.pop()), float(St.pop())
            St.append(a+b)
        elif i == '-':
            b, a = float(St.pop()), float(St.pop())
            St.append(a-b)
        elif i == '*':
            b, a = float(St.pop()), float(St.pop())
            St.append(a*b)
        elif i == '/':
            b, a = float(St.pop()), float(St.pop())
            St.append(a/b)
        else:
            St.append(i)

    return St[0]


while True:
    try:
        s = raw_input().split()

    except EOFError:
        break

    print Calculate_RPN(s)

中間記法で記述された数式を逆ポーランド記法に変換する

この変換もスタックを用いて行うことが出来ます。

次のような手順で変換できます。

ほぼここ(http://knowledge.sakura.ad.jp/etc/220/)に書いてあることのコピペ。

  • 数式を左から順に読み込む
  • 数値だったら出力だったらスタックに積む だったらスタック上の演算子が出てくるまで出力しは削除する
  • 演算子だったらスタックに積む
    • スタックトップの演算子の優先順位がスタックに積まれる演算子より高ければそれを出力する
  • 数式を最後まで読み込んだ後、スタック上に演算子が残っていればそれをスタックが空になるまで順に出力する

逆ポーランド記法では演算子の優先順位は左に行くほど高くなります。

中間記法の数式を左から読み込んでいき演算子をスタックに積んだとき、+-*/などの同じ優先順位のものは先にスタックに入っているものの方が当然優先順位は高くなります。(中間記法では同じ優先順位なら左から計算が行われるから) (それはそう)

空白区切りなしで中間記法で表された数式1行が与えられ逆ポーランド記法に変換したものを出力するプログラムは次のように書けます。

動けばいいやと思って書いたクッソ汚いコードなのであまり参考にしないほうが良いと思います。

#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <cstdlib>
#include <cctype>

using namespace std;

void str2arr(string s, string A[]) {
    int n = 0;
    string tmp = "";

    for (int i = 0; s[i] != '=' ; i++) {
        if ('0' <= s[i] && s[i] <= '9') {
            tmp += s[i];
        }
        else {
            if (tmp != "") { 
                A[n++] = tmp;
                tmp = "";
            }
            A[n++] = s[i];
        }
    }
    if (tmp != "") { A[n++] = tmp; }
    A[n++] = "=";
}

void Generate_RPN(string A[], string B[]) {
    map<string, int> table;
    stack<string> St;
    table["*"] = 1;
    table["/"] = 1;
    table["+"] = 0;
    table["-"] = 0;
    table["("] = -1;
    table[")"] = -1;

    int j = 0;
    for (int i = 0; A[i] != "="; i++) {
        if ('0' <= A[i][0] && A[i][0] <= '9') {
            B[j++] = A[i];
        }
        else if (A[i] == "(") {
            St.push(A[i]);
        }
        else if (A[i] == ")") {
            while (St.top() != "(") {
                B[j++] = St.top(); St.pop();
            }
            St.pop();
        }
        else {
            while ((!St.empty()) && (table[St.top()] >= table[A[i]])) {
                B[j++] = St.top(); St.pop();
            }
            St.push(A[i]);
        }
    }
    while (!St.empty()) {
        B[j++] = St.top(); St.pop();
    }
    B[j] = "=";
}

int main() {
    string A[100], B[100];
    string s;

    cin >> s;
    s += "=";

    str2arr(s, A);
    Generate_RPN(A, B);

    for (int i = 0; B[i] != "="; i++) {
        cout << B[i];
        cout << (B[i+1] == "=" ? "\n" : " ");
    }

    return 0;
}
# coding: utf-8

# Convert String to List
def String2List(s):
    L = []; tmp = ""
    for i in s:
        if i.isdigit():
            tmp += i
        else:
            if tmp != "":
                L.append(tmp)
                tmp = ""
            L.append(i)
    if tmp != "":
        L.append(tmp)

    return L

# generate Reverse Polish Notation
def Generate_RPN(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)

    while len(S) != 0:
        L2.append(S.pop())

    return L2

s = raw_input()
print " ".join(Generate_RPN(String2List(s)))

中間記法で記述された数式を評価する

先に書いた2つのコードを組み合わせれば中間記法で記述された数式の評価が出来ます。

AOJ0109: Smart Calculator

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109&lang=jp

この問題を解いてみましょう。

C++逆ポーランド記法の数式を評価するとき全てdoubleで計算して最後にintにキャストするみたいにやったら Wrong Answer が出て辛かったです。

  • C++による解答例
#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <cstdlib>
#include <cctype>

using namespace std;

void str2arr(string s, string A[]) {
    int n = 0;
    string tmp = "";

    for (int i = 0; s[i] != '=' ; i++) {
        if ('0' <= s[i] && s[i] <= '9') {
            tmp += s[i];
        }
        else {
            if (tmp != "") { 
                A[n++] = tmp;
                tmp = "";
            }
            A[n++] = s[i];
        }
    }
    if (tmp != "") { A[n++] = tmp; }
    A[n++] = "=";
}

void Generate_RPN(string A[], string B[]) {
    map<string, int> table;
    stack<string> St;
    table["*"] = 1;
    table["/"] = 1;
    table["+"] = 0;
    table["-"] = 0;
    table["("] = -1;
    table[")"] = -1;

    int j = 0;
    for (int i = 0; A[i] != "="; i++) {
        if ('0' <= A[i][0] && A[i][0] <= '9') {
            B[j++] = A[i];
        }
        else if (A[i] == "(") {
            St.push(A[i]);
        }
        else if (A[i] == ")") {
            while (St.top() != "(") {
                B[j++] = St.top(); St.pop();
            }
            St.pop();
        }
        else {
            while ((!St.empty()) && (table[St.top()] >= table[A[i]])) {
                B[j++] = St.top(); St.pop();
            }
            St.push(A[i]);
        }
    }
    while (!St.empty()) {
        B[j++] = St.top(); St.pop();
    }
    B[j] = "=";
}

int Calculate_RPN(string s[]) {
    stack<double> St;
    double a, b;

    for (int i = 0; s[i] != "="; i++) {
        if (s[i] == "+") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a+b);
        }
        else if (s[i] == "-") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a-b);
        }
        else if (s[i] == "*") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a*b);
        }
        else if (s[i] == "/") {
            b = int(St.top()); St.pop();
            a = St.top(); St.pop();
            St.push(a/b);
        }
        else {
            St.push(atoi(s[i].c_str()));
        }
    }
    return int(St.top());
}

int main() {
    int n;
    string A[100], B[100];
    string in;

    cin >> n;

    while (n--) {
        cin >> in;
        str2arr(in, A);
        Generate_RPN(A, B);
        cout << Calculate_RPN(B) << endl;
    }

    return 0;
}
# coding: utf-8

# Convert String to List
def String2List(s):
    L = []; tmp = ""
    for i in s:
        if i.isdigit():
            tmp += i
        else:
            if tmp != "":
                L.append(tmp)
                tmp = ""
            L.append(i)
    if tmp != "":
        L.append(tmp)

    return L

# generate Reverse Polish Notation
def Generate_RPN(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)

    while len(S) != 0:
        L2.append(S.pop())

    return L2

def Calculate_RPN(L):
    St = []
 
    for i in L:
        if i == '+':
            St.append(int(St.pop()) + int(St.pop()))
        elif i == '-':
            St.append(-int(St.pop()) + int(St.pop()))
        elif i == '*':
            St.append(int(St.pop()) * int(St.pop()))
        elif i == '/':
            a = int(St.pop())
            b = float(St.pop())
            St.append(b/a)
        else:
            St.append(i)
 
    return St[0]


n = int(raw_input())

for _ in xrange(n):
    s = raw_input()
    print int(Calculate_RPN(Generate_RPN(String2List(s[:-1]))))

感想

やるだけなのにバグを埋め込みまくってコードを書くのにすごい時間がかかって辛かったです。あと一応AOJのシステムテストは通りましたが間違ってる可能性も大いにあるのでご注意ください。

AOJ0109: Smart Calculatorの他の人の解答を見てみたらみんな全然違う解き方をしていたのでみんなの解き方での実装もそのうちやりたいと思いました。

これ(https://gist.github.com/draftcode/1357281)とかめっちゃ参考になりそう。

参考文献