逆ポーランド記法による計算プログラムの負の整数対応版

昨日できそうと書いたので改造してみた。

//------------------------
// ヘッダファイル
//------------------------
#include <stdio.h>
#include <ctype.h>

//------------------------
// マクロ
//------------------------
#define STACK 10

//------------------------
// 主処理
//------------------------
int main(void)
{
  //--- 宣言
  int stack[STACK]; // スタック
  int stack_n;  // スタック位置
  int sum; // 合計
  int digit_f; // 数が連続した場合のフラグ
  int k;  // 一時変数
  int minus_f;  // -に数字が続くか
  char ch;  // 文字取り出し用
  //--- 初期化
  stack_n = 0;
  digit_f = 0;
  minus_f = 0;
  //--- 入力
  printf("計算式を入力して下さい(逆ポーランド記法)\n");
  while( (ch = getchar()) != '\n' ) { // 改行がくるまで入力を続ける
    //--- 計算
    if( isdigit(ch) ) { // 文字が整数('0'～'9')までの場合
      if( digit_f ) { // 整数が連続したかの判定
        stack[stack_n] = stack[stack_n] * 10 + (ch - '0');  // 連続した場合元の数に10かけてたす
      } else if( minus_f ){
        stack[stack_n] = -1 * (ch - '0');
        minus_f = 0;
      } else {
        stack[stack_n] = (ch - '0');
        digit_f++;
      }
    }
    if( isspace(ch) ) { // 空白なら
      if( digit_f ) { // 前の文字が整数だった場合
        stack_n++;
        digit_f = 0;
      }
      if( minus_f ) {
        //printf("-\n");  // デバッグ用
        if( stack_n > 1 ) {
          stack_n--;
        }
        stack[stack_n-1] -= stack[stack_n];
        stack[stack_n] = 0;
        minus_f = 0;
      }
    }
    if( ch == '+' ) { // 足し算
      //printf("+\n");  // デバッグ用
      if( stack_n > 1 ) {
        stack_n--;
      }
      stack[stack_n-1] += stack[stack_n];
      stack[stack_n] = 0;
    }
    if( ch == '-' ) { // 引き算
      minus_f++;
    }
    if( ch == '*' ) { // 掛け算
      //printf("*\n");  // デバッグ用
      if( stack_n > 1 ) {
        stack_n--;
      }
      stack[stack_n-1] *= stack[stack_n];
      stack[stack_n] = 0;
    }
    if( ch == '/' ) { // 割り算
      //printf("/\n");  // デバッグ用
      if( stack_n > 1 ) {
        stack_n--;
      }
      stack[stack_n-1] /= stack[stack_n];
      stack[stack_n] = 0;
    }
     /* for( k=0; k<=stack_n; k++ ) {  // デバッグ用
      printf("%d ",stack[k]);
    }
    printf("\n"); */
  }
  if( minus_f ) {
    //printf("-\n");  // デバッグ用
    if( stack_n > 1 ) {
        stack_n--;
      }
    stack[stack_n-1] -= stack[stack_n];
    stack[stack_n] = 0;
    minus_f = 0;
  }
  //--- 出力
  printf("%d\n",stack[0]);
  //--- 終了
  return 0;
}

改造する際に数が二つの場合うまく処理されないバグを見つけた。
最後の演算子が'-'の場合うまく処理されないので終わりに処理を書いた。

C言語による正の整数の四則演算が可能な逆ポーランド記法計算

なんとなく逆ポーランド記法を使ってみたのでC言語による逆ポーランド記法計算プログラムを作ってみた。

//------------------------
// ヘッダファイル
//------------------------
#include <stdio.h>
#include <ctype.h>

//------------------------
// マクロ
//------------------------
#define STACK 10

//------------------------
// 主処理
//------------------------
int main(void)
{
  //--- 宣言
  int stack[STACK]; // スタック
  int stack_n;  // スタック位置
  int sum; // 合計
  int digit_f; // 数が連続した場合のフラグ
  int k;  // 一時変数
  char ch;  // 文字取り出し用
  //--- 初期化
  stack_n = 0;
  digit_f = 0;
  //--- 入力
  printf("計算式を入力して下さい(逆ポーランド記法)\n");
  while( (ch = getchar()) != '\n' ) { // 改行がくるまで入力を続ける
    //--- 計算
    if( isdigit(ch) ) { // 文字が整数('0'～'9')までの場合
      if( digit_f ) { // 整数が連続したかの判定
        stack[stack_n] = stack[stack_n] * 10 + (ch - '0');  // 連続した場合元の数に10かけてたす
      } else {
        stack[stack_n] = (ch - '0');
        digit_f++;
      }
    }
    if( isspace(ch) ) { // 空白なら
      if( digit_f ) { // 前の文字が整数だった場合
        stack_n++;
        digit_f = 0;
      }
    }
    if( ch == '+' ) { // 足し算
      //printf("+\n");  // デバッグ用
      if( stack_n > 1 ) {
        stack_n--;
      }
      stack[stack_n-1] += stack[stack_n];
      stack[stack_n] = 0;
    }
    if( ch == '-' ) { // 引き算
      //printf("-\n");  // デバッグ用
      if( stack_n > 1 ) {
        stack_n--;
      }
      stack[stack_n-1] -= stack[stack_n];
      stack[stack_n] = 0;
    }
    if( ch == '*' ) { // 掛け算
      //printf("*\n");  // デバッグ用
      if( stack_n > 1 ) {
        stack_n--;
      }
      stack[stack_n-1] *= stack[stack_n];
      stack[stack_n] = 0;
    }
    if( ch == '/' ) { // 割り算
      //printf("/\n");  // デバッグ用
      if( stack_n > 1 ) {
        stack_n--;
      }
      stack[stack_n-1] /= stack[stack_n];
      stack[stack_n] = 0;
    }
    /* for( k=0; k<=stack_n; k++ ) {  // デバッグ用
      printf("%d ",stack[k]);
    }
    printf("\n"); */
  }
  //--- 出力
  printf("%d\n",stack[0]);
  //--- 終了
  return 0;
}

if( ch = '+' )と書いてしまいとても手こずった。
このプログラムでは正の整数のみしか扱えないが、'-'のあと空白なしに整数がくれば"-整数"をスタックするようにすれば負の整数も扱えるようになるかもしれない。

2014/10/21追記
数が二つだとうまく処理されないのを修正。

ティッシュを作成するアプリ(Ruby)

Rubyでティッシュを作成するだけのクソプログラムを作成してみた。

name = (0...3).map{ (65 + rand(26)).chr }.join
File.open("ティッシュ."+name,"w").close

このプログラムはティッシュ.(ランダム３文字の大文字)というファイルを作成するだけのプログラムである。
それだけです。
本来はティッシュを作った後ティッシュをゴミ箱に移動させるように考えていたが、ゴミ箱に入れるのは技術不足より断念した。

C言語におけるボゴソート

ボゴソートなる量子コンピュータにおいては優秀なソートとなる可能性があるソートがあるらしいのでリハビリがてら実装してみることにした。

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  int array[10];  // 配列
  int t;  // 格納変数
  int i;  // 反復変数
  int size; // 入力数
  int f;  // 条件変数
  int r1,r2;  // ランダム
  
  size = 0;  // 入力数の初期化
  
  while( 1 ) {  // -1が出るまで入力
    scanf("%d",&t);
    if( t == -1 ) { break; }
    array[size] = t;
    size++;
  }
  
  while( 1 ) {  // ボゴソート
    f = 0;  // 条件の初期化
    for( i=0; i<size-1; i++ ) {
      if( array[i] > array[i+1] ) {
        f = 1;
      }
    }
    if( f ) { // ランダムに入れ替える
      r1 = (int)((rand()/(RAND_MAX+1.0))*size);
      r2 = (int)((rand()/(RAND_MAX+1.0))*size);
      
      t = array[r1]; 
      array[r1] = array[r2];
      array[r2] = t;
    } else {
      break;
    }
  }
  
  for( i=0; i<size; i++ ) { // 列挙
    printf("%d ",array[i]);
  }
  
  return 0;
}

でたらめに交換していくようだ。
調べると無限の猿定理とか出てきて奥深い...???
でたらめに交換していくという単純なソートなので覚えていても損はない？(実用的ではないが)

2015.05.01 乱数が適当すぎるので修正

C言語における３つのソートの時間計測

先日の３つのソートの時間計測をしてみた。
計測方法は

#include <time.h>
clock_t start,end;
(冒頭) start = clock();
(最後) end = clock();
       printf("%.2f\n",(double)(end-start)/CLOCKS_PER_SEC);

を用いる。
入力は

10 9 8 7 6 5 4 3 2 1 -1

である。

バブルソート

9.42

選択ソート

6.28

挿入ソート

5.79

一般的に言われるように処理時間は
バブルソート>選択ソート>挿入ソート
となった。

C言語における挿入ソート

ほぼコピペだが実装。

#include <stdio.h>

int main(void)
{
  int array[10];  // 配列
  int t;  // 格納変数
  int k1,k2,k3;  // 反復変数
  
  k1 = 0;  // 反復変数の初期化
  
  while( 1 ) {  // -1が出るまで入力
    scanf("%d",&t);
    if( t == -1 ) break;
    array[k1] = t;
    k1++;
  }
  
  for( k2=1; k2<k1; k2++ ){ //挿入ソート
    t = array[k2];
    for( k3=k2; k3>0 && array[k3-1]>t; k3-- ){
      array[k3] = array[k3-1];
    }
    array[k3] = t;
  }
  
  for( k2=0; k2<k1; k2++ ){ // 列挙
    printf("%d ",array[k2]);
  }
  
  return 0;
}

挿入ソートは条件が合致すれば要素を前に挿入して残りを後ろに押し出していくイメージだろうか。

かなり単純になった。

C言語におけるバブルソート

ほぼコピペだがバブルソートを実装してみた。

#include <stdio.h>

int main(void)
{
  int array[10];  // 配列
  int t;  // 格納変数
  int k1,k2,k3;  // 反復変数
  
  k1 = 0;  // 反復変数の初期化
  
  while( 1 ) {  // -1が出るまで入力
    scanf("%d",&t);
    if( t == -1 ) break;
    array[k1] = t;
    k1++;
  }
  
  for( k2=0; k2<k1-1; k2++ ){
    for( k3=k1-1; k3>k2; k3-- ){
      if( array[k3-1] > array[k3] ){
        t = array[k3];
        array[k3] = array[k3-1];
        array[k3-1] = t;
      }
    }
  }
  
  for( k2=0; k2<k1; k2++ ){ // 列挙
    printf("%d ",array[k2]);
  }
  
  return 0;
}

選択ソートが前から攻めていくイメージならバブルソートは後ろから前から挟んでいくというイメージだろうか。
変数が3つ減ったので単純になった。

とりあえずよくわからない。