1桁の正整数と加算、乗算、括弧(入れ子なし)に対応した電卓

Question

前提・実現したいこと

C言語で電卓を作っています。たとえば1+3*(2+4)のように、一桁の正整数、加算、乗算、括弧（入れ子なし）からなる式が入力された時、計算結果を画面に表示するプログラムを作りたいです。
ここに質問の内容を詳しく書いてください。
入力された式は一旦文字列型の配列に格納し、その後整数型の配列に変換します。この際、後で探索がしやすいように'('は-1,')'は-2,'+'は-3,'*'は-4として変換しています。
ここからが問題で、たとえば上の式であれば、まず(2+4)を計算すると思います。そのように、選択した部分の計算を実行するにはどうしたら良いでしょうか。()や+,といった演算子に応じて範囲を選択し、該当部分の計算を実行するというアルゴリズムでいこうと思っています。
まずは()を探索し、()内の加算、乗算を行います。
→ここで役目を終えた括弧を消去したいのですが、それはどのようにしたら良いでしょうか。
次に加算、乗算についてです。
たとえば
a[i]の演算子が+だった場合、a[i-1]=a[i-1]+a[i+1];
a[i]の演算子がだった場合、a[i-1]=a[i-1]a[i+1];
とすれば計算結果は得られますが、この後の処理はどうすれば良いでしょうか。
配列を左にどんどん詰めていくというのが基本的な考え方だと思うのですが、ではどのタイミングで詰めるのかがわかりません。
演算子がなくなるまで乗算を実行、その後演算子+がなくなるまで加算を実行というプロセスでいいことはわかります。
どの処理を関数として定義するかが全くわかりません。
ご回答のほどよろしくお願いいたします。

■■な機能を実装中に以下のエラーメッセージが発生しました。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

#include <stdio.h>
int main(void)
{
char formula1[100];
printf("式を入力してください:" );
gets(formula1);//ひとまず文字型の配列に数字等を格納

//型の変換
int formula2[100];//変換後の数値、記号を格納する配列
for (int i = 0; i < 100; i++) {
if(formula1[i]=='('){formula2[i]=-1;}
else
if(formula1[i]==')'){formula2[i]=-2;}
else
if(formula1[i]=='+'){formula2[i]=-3;}
else
if(formula1[i]=='*'){formula2[i]=-4;}
else
{formula2[i]=formula1[i]-'0';}//数字なら数値に変換
}

}
c言語```ここに言語名を入力
ソースコード

### 試したこと

ここに問題に対して試したことを記載してください。

### 補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[y_waiwai]

このままではコードが読みづらいので、質問を編集し、<code>ボタンを押し、出てくる’’’の枠の中にコードを貼り付けてください

[dodox86]

> ()や+,*といった演算子に応じて範囲を選択し、該当部分の計算を実行するというアルゴリズムでいこうと思っています。

これはまだアルゴリズムと言えるほどのものではなく、いわば「方針」です。まず、カッコは考えず入力された文字列の左端から順番に四則演算だけでもできるでしょうか。それだけでも恐らく初心の方には難しいものですし、それがまだできない場合、カッコを考えた優先順位付きの計算は無理だと思います。現状ですと、分からないことがほとんどのようでほぼ丸投げの印象を受けます。

[jimbe]

少なくとも括弧の無い足し算だけ掛け算だけの式は計算出来て、括弧を付けての式をそれなりの内部構造に変換して壁に当たった…程度までは頑張って欲しいものですが。

Answer 1

正規表現を使えばこうなるでしょう。

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

regex_t preg[3];

void replace(char *f, int so, int eo, int v) {
  sprintf(&f[so], "%d", v);
  strcat(f, &f[eo]);
}

int calc(char *f) {
  regmatch_t match[3];
  // ()
  while(!regexec(&preg[0], f, 1, match, 0)) {
    f[(int)match[0].rm_eo-1] = '\0';
    int v = calc(&f[match[0].rm_so+1]);
    replace(f, match[0].rm_so, match[0].rm_eo, v);
  }
  // *
  while(!regexec(&preg[1], f, 3, match, 0)) {
    int v1 = (int)strtol(&f[match[1].rm_so], NULL, 10);
    int v2 = (int)strtol(&f[match[2].rm_so], NULL, 10);
    int v = v1 * v2;
    replace(f, match[0].rm_so, match[0].rm_eo, v);
  }
  // +
  while(!regexec(&preg[2], f, 3, match, 0)) {
    int v1 = (int)strtol(&f[match[1].rm_so], NULL, 10);
    int v2 = (int)strtol(&f[match[2].rm_so], NULL, 10);
    int v = v1 + v2;
    replace(f, match[0].rm_so, match[0].rm_eo, v);
  }
  return atoi(f);
}

void test(char *formula) {
  printf("f=%s\n", formula);

  regcomp(&preg[0], "\([^(]+\)", REG_EXTENDED|REG_NEWLINE); // ()
  regcomp(&preg[1], "([0-9]+)\*([0-9]+)", REG_EXTENDED|REG_NEWLINE); // *
  regcomp(&preg[2], "([0-9]+)\+([0-9]+)", REG_EXTENDED|REG_NEWLINE); // +

  char *f = malloc(strlen(formula)+1);
  strcpy(f, formula);

  int a = calc(f);
  printf("a=%d\n", a);

  free(f);

  regfree(&preg[2]);
  regfree(&preg[1]);
  regfree(&preg[0]);
}

int main(int argc, char *argv[]) {
  test("1+2");
  test("2*3");
  test("1+2*3");
  test("(1+2)*3");
  test("1+3*(2+4)");
}

f=1+2
a=3
f=2*3
a=6
f=1+2*3
a=7
f=(1+2)*3
a=9
f=1+3*(2+4)
a=19

参考までに、スタックでベタに逆ポーランド記法利用時はこんな感じかと。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

/*
 * スタック
 */

#define STACK_MAX 100
int istack[STACK_MAX];
char *cstack[STACK_MAX];
int sp;

void cpush(char *token) {
  cstack[sp++] = token;
}

char *cpop() {
  return sp > 0 ? cstack[--sp] : NULL;
}

char *cpeek() {
  return sp > 0 ? cstack[sp-1] : NULL;
}

void ipush(int value) {
  istack[sp++] = value;
}

int ipop() {
  return sp > 0 ? istack[--sp] : INT_MAX;
}

/*
 * 式分解(一文字ずつ文字列化)
 */

#define BUFFER_MAX 1024
char buf[BUFFER_MAX];

char **splitFormula(char *formula) {
  memset(buf, 0, sizeof(buf));
  char **tokens = malloc((strlen(formula)+1)*sizeof(char*));
  char *p = buf;
  for(int i=0; i<strlen(formula); i++) {
    *p = formula[i];
    tokens[i] = p;
    p += 2;
  }
  tokens[strlen(formula)] = NULL;
  return tokens;
}

/*
 * RPN化
 */

int priority(char *op) {
  if(*op == '*') return 1;
  if(*op == '+') return 0;
  return -1;
}

void toRPN(char *tokens[]) {
  sp = 0;
  int j = 0;
  for(int i=0; tokens[i]!=NULL; i++) {
    char *token = tokens[i];
    if(isdigit((int)*token)) {
      tokens[j++] = token;
    } else if(*token == '(') {
      cpush(token);
    } else if(*token == ')') {
      for (char *t; (t=cpop())!=NULL && *t!='('; ) tokens[j++] = t;
    } else {
      while(cpeek()!=NULL && priority(cpeek()) >= priority(token)) tokens[j++] = cpop();
      cpush(token);
    }
  }
  for (char *t; (t=cpop())!=NULL; ) tokens[j++] = t;
  tokens[j] = NULL;
}

/*
 * 計算
 */

int calc(char *rpn[]) {
  sp = 0;
  for(int i=0; rpn[i]!=NULL; i++) {
    if(isdigit((int)*rpn[i])) {
      ipush(atoi(rpn[i]));
    } else {
      int v2 = ipop();
      int v1 = ipop();
      if(*rpn[i] == '*') {
        ipush(v1 * v2);
      } else if(*rpn[i] == '+') {
        ipush(v1 + v2);
      }
    }
  }
  return ipop();
}

/*
 * 確認用
 */

void printTokens(char *tokens[]) {
  for(int i=0; tokens[i]!=NULL; i++) printf(" %s", tokens[i]);
  printf("\n");
}

void test(char *formula) {
  char **expr = splitFormula(formula);
  printTokens(expr);
  toRPN(expr);
  printTokens(expr);
  printf("%d\n", calc(expr));
  free(expr);
}

int main(int argc, char *argv[]) {
  test("1+2");
  test("2*3");
  test("1+2*3");
  test("(1+2)*3");
  test("1+3*(2+4)");
}

 1 + 2
 1 2 +
3
 2 * 3
 2 3 *
6
 1 + 2 * 3
 1 2 3 * +
7
 ( 1 + 2 ) * 3
 1 2 + 3 *
9
 1 + 3 * ( 2 + 4 )
 1 3 2 4 + * +
19

Answer 2

いろいろなやり方があります。たとえば、これはどうでしょうか？

#include <stdio.h>  // fgets, printf

char a[1000];
int i, c, expr(void);

int factor(void)
{
	int v = 0;
	c = a[i++];
	if (c == '(') {
		v = expr();
		if (c == ')') c = a[i++];
		else c = 1;
	}
	else if (c >= '0' && c <= '9') {
		v = c - '0';
		c = a[i++];
	}
	else c = 1;
	return v;
}

int term(void)
{
	int v = factor();
	while (c == '*') v *= factor();
	return v;
}

int expr(void)
{
	int v = term();
	while (c == '+') v += term();
	return v;
}

int main(void)
{
	fgets(a, sizeof a, stdin);
	int v = expr();
	if (c == '\n' || c == 0) printf("%d\n", v);
	else puts("error");
}

ポインタも構造体もないから、むずかしくないと思うんですが、どうでしょうか？

追記
逆ポーランド記法に変換してから計算するやり方です。

#include <stdio.h>  // puts, printf

const char *a;  char b[1000];  int i, j, c;  void expr(void);

void factor(void)
{
	c = a[i++];
	if (c == '(') expr(), c = c == ')' ? a[i++] : 1;
	else if (c - '0' <= 9u) b[j++] = c, c = a[i++];
	else c = 1;
}

void term(void) { for (factor(); c == '*'; b[j++] = '*') factor(); }

void expr(void) { for (term(); c == '+'; b[j++] = '+') term(); }

int calc(void)
{
	int s[100], p = 0;  // s: stack, p: stack pointer
	for (int k = 0; k < j; k++)
		if (b[k] == '+') p--, s[p-1] += s[p];
		else if (b[k] == '*') p--, s[p-1] *= s[p];
		else s[p++] = b[k] - '0';
	return s[0];
}

void test(const char *s)
{
	puts(a = s);
	i = j = 0;
	expr();
	if (c) puts(" error");
	else {
		for (int k = 0; k < j; k++) printf(" %c", b[k]);
		printf(" : %d\n", calc());
	}
}
	
int main(void)
{
	test("1+2");
	test("2*3");
	test("1+2*3");
	test("(1+2)*3");
	test("1+3*(2+4)");
}

Answer 3

()や+,*といった演算子に応じて範囲を選択し、該当部分の計算を実行する

という話を，「計算を実行する範囲を２つのポインタで示す」という形でやってみました．

話を簡単にするため，メモリを動的に確保とかはせず，作業用のバッファは「十分なサイズだけ」ローカル変数で用意する形にしてあります．
また，

一桁の正整数、加算、乗算、括弧（入れ子なし）

という条件であることを前提とし，エラーチェックはまともに入ってません．

//文字列の一部．範囲 [begin, end) として表す
typedef struct SubStr
{
	const char *begin;  //先頭の文字を指す
	const char *end;  //末尾の文字の次を指す
} SubStr;

//（プロトタイプ宣言）
int EvalStr( const char *begin, const char *end );

//[begin, end) の範囲から c を探してその場所を返す．
//見つからない場合は end を返す．
const char *find( char c, const char *begin, const char *end )
{
	const char *p = begin;
	for( ; (p!=end) && ((*p)!=c); ++p ){}
	return p;
}

//文字列 [begin, end) をバラす．
//ただし，括弧で囲まれた範囲の内側まではバラさらない．
//結果は pBuff の先頭側から突っ込まれる．(pBuff は十分なサイズの領域を指すこと)
//突っ込んだ個数を返す．
int ParseToSubStrs( SubStr *pBuff, const char *begin, const char *end )
{
	int n = 0;
	const char *p = begin;
	while( p != end )
	{
		if ( *p == '(' )
		{// '(' と ')' で囲まれた範囲（括弧の内側）を１つの結果とする
			const char *pRightParenthese = find( ')', p+1, end );
			if( pRightParenthese == end )
			{
				printf( "Error : Left_parenthese without Right_parenthese" );
				exit(0);
			}
			pBuff[n].begin = p+1;
			pBuff[n].end = pRightParenthese;
			p = pRightParenthese + 1;
		}
		else
		{//※ここに来るとき，pが指すのは，数字(一桁限定なので１文字)か演算子(１文字)であるハズ
			pBuff[n].begin = p;
			pBuff[n].end = p+1;
			++p;
		}
		++n;
	}
	return n;
}

//単一の SubStr の内容を整数値に解釈する．
int EvalSubStr_to_Int( SubStr SS )
{
	if( SS.end - SS.begin > 1 )
	{	return EvalStr( SS.begin, SS.end );	}
	else
	{	return *SS.begin - '0';	}	//※１桁の数値であることを決め打ちで処理
}

// nSS 個の連続した SubStr 群を整数値に解釈する．
int EvalSubStrs( SubStr *pSSs, int nSS )
{
	if( nSS == 1 )
	{	return EvalSubStr_to_Int( pSSs[0] );	}

	for( int i=1; i<nSS-1; ++i )
	{
		if( *pSSs[i].begin == '+' )
		{
			int Left = EvalSubStrs( pSSs, i );
			int Right = EvalSubStrs( pSSs+(i+1), nSS-(i+1) );
			return Left + Right;
		}
	}
	
	for( int i=1; i<nSS-1; ++i )
	{
		if( *pSSs[i].begin == '*' )
		{
			int Left = EvalSubStrs( pSSs, i );
			int Right = EvalSubStrs( pSSs+(i+1), nSS-(i+1) );
			return Left * Right;
		}
	}
	printf( "Error\n" );
	exit( 0 );
}

//数式文字列 [begin, end) の内容を評価して結果値を返す．
int EvalStr( const char *begin, const char *end )
{
	SubStr SubStrs[16];  //※サイズはてきとー
	int nSubStr = ParseToSubStrs( SubStrs, begin, end );  //文字列をバラして…
	return EvalSubStrs( SubStrs, nSubStr );  //評価する
}

//---------------

//式１個分をやってみるテスト
void Test( const char *Str )
{
	int n = (int)strlen( Str );
	printf( "%s = %d\n", Str, EvalStr( Str, Str+n ) );
}

int main(void)
{//いろんな式でテスト
	Test( "1+3*(2+4)" );
	Test( "(3+9)*(2*4)" );
	Test( "4+7*2" );
	Test( "4*1*5+2" );
	return 0;
}

Answer 4

まず、プログラミングは「こう書けばいい」というものではありません。
現実世界のシミュレーションです。

(おそらく質問者さんはお気づきかもしれませんが)

なので、現実世界でならどうするかを考えるのです。
今回の場合、割と楽な気がします。

かっこが使われていますが、入れ子はなく、かつ数字は常に一桁であることが前提のようですから。

F = 1+3*(2+4)

とします。

このFを計算する場合、現実世界ではどのようにしますか？

私なら、『かっこから先に計算』します。

1+3*(2+4)
= 1+3*6

ということは、『(…)で囲まれている式を先に計算』するということです。

構造をよくみてください。必ず、“(”と“)”の数は同じであるはずです。そして、入れ子ではない。

ということは、

1. 先頭から末尾までの中で最初の“(“を探す
2. “(”があったら
    2.1. “)”の場所を探す
    2.2. (1)の場所から(2.1)の場所まで切り出す
    2.3. 計算する
    2.4. 置き換える

のような感じになるかと思います。

…発想そのものはここまでできているようですね。

あとは実現方法。

現実世界で考えてみてください。質問者さんは脳内ではどのようにやっていますか？
おそらく、かっこの中を先に計算して、そこをYとかのような別の値に変換しているのではないかなと。

F = 1+3*(2+4)

一番優先順位の高い計算はかっこ付きなので”(“を探す。それで囲まれている部分を探す。

(2+4)の計算結果をYと置くと、

F = 1+3*Y

と置き換える。

これ以上かっこ付きはないので次の演算子へ。次に優先順位の高いものは掛け算なので、
*を探す。そうすると3*Yがヒット。これを計算する。
この計算結果をXと置くと、

F = 1+X

となる。これ以上優先するものはないので以降は先端から計算していく。

的な感じになっているはずです。

もちろん、実際に使う文字や式とかは違いますが。

Yとかを使わずに数字にするのが普通かもしれませんが。

とにかく、『元の計算式の特定の部分を書き換える』的な処理を脳内でしているはずです。
上記で言えば(2+4) を Y とおく感じの。実際にはYではなく、2+4の結果、6と置き換える感じです。

アルゴリズムっぽく考えると、

1. “(”の場所を調べる(int beginとする)
2. “)”の場所を調べる(int endとする)
3. beginからendまでの文字列を切り出す
4. (3)を計算(int tempとする)
5. 元の文字列のbeginからendまでを(4)の値に置き換える

これを優先順位が高いものがなくなるまで繰り返す

的な感じになるかなと。

つまり、『切り出し』→『計算』→『元の文字列に置き換え』的な処理ですね。入れ子になっていると面倒ですが、それでも発想は同じかも。

---

[追記0]

あと、質問では“+”とかを-1やらなんやらに置き換えていますが、それはしなくてもできるはずです。

式全体をFとしたとき、Fは単なる文字列です。
文字列は文字が0文字以上連なったものです。
だから配列で表現するのです。

“1”も“+”も文字です。

それに、出てくる数字に関しては(かっこ内でないなら)常に一桁ですよね。

ということは、

<数字><演算子><数字><演算子>…

となっているはずです。

よくみると、数字と演算子が交互に出ています。となると、かっこ内をすでに計算した後という前提であれば、

1. 文字数分ループ
    1.1. 現在の文字を取得
    1.2. 現在の文字が“+”なら
        1.2.1. 前後の文字をそれぞれ整数にして
        1.2.2. 計算する
    1.3. (そうじゃなくて) “-”なら
         …

のような感じになるかなと。

ただし、”1”と 1は別物です。なので『文字を整数にする処理』が必要になります。文字列ではありません。

これに関しては調べてください。

上で切り出したかっこ内の式もこの考えを適用できます。

ーーーー
[追記0:オフトピ]

修正依頼のところに書くべき内容ですが、質問者さんは無視しているのか、やり方がわからないのかわかりませんが、改善されていないようなので書いておきます。

コードは”<code>”または”<コード>”のボタンを押して出てくるやつの中にかきましょう。
ご自分の質問にあるコードと回答者のコード等を比較してみましょう。今のままでは非常に読みづらいです。ひらがなでしかも句読点なしの文章を読まされるようなものです。

知っていて我を押し通すつもりなら次からは回答者が一気に減ると思います。そうすると質問者さんにとって有用な情報も得られなくなります。

知らなかったのなら、これを機にやってみましょう。質問は修正できるので修正してください。

[私が「修正依頼を無視している」と考えた根拠]

過去質問(一件ですが)では、ある方がご指摘なさっていますが、それを無視しています。
もしかしたらMarkdownとかの存在がわからない可能性もあるとは思いますが、流石にアニメーションで提示されているのでそれは無いかなと。

仮に「質問を編集できるということが分かっていなかった」だけだとしても、二回目以降の質問でも同じようなことをやっています。なので「改善する気が無い」人なのかなと勘繰ってみたり。

※このオフトピ追記は質問が修正され次第、削除する予定です。

Comments

[dodox86]

> [追記0:オフトピ]
> 修正依頼のところに書くべき内容ですが、質問者さんは無視しているのか、やり方がわからないのかわかりませんが、改善されていないようなので書いておきます。

質問の投稿が[2021/10/26 02:32]で、「質問への追記・修正、ベストアンサー選択の依頼」欄においてマークダウンを使用して見易くしましょうとの指摘が[2021/10/26 07:08]です。無視を疑うにはさすがに急ぎ過ぎなのではないでしょうか。
（なお、ご回答への低評価は私がしたものではありません）

[K_3578]

横からですが

>さすがに急ぎ過ぎなのではないでしょうか。

https://teratail.com/questions/362341
での追記修正依頼でのやり取りを見る限りでは意図的に無視しているかそもそもMarkdownを理解していないのかと思ったのでこの指摘は質問者に気づいて貰うためにも必要だと私は思います

[fana]

> 必ず、”(“と”(“の数は同じであるはずです。

誤記っす．一方は ')' ですね．

あと，私も割と空行を多用しちゃう方だけど，そんな私から見てもちょっと空行が多いなぁと感じます．
段落というか話の切れ目ではない箇所に空行が入るとちょっと読み難いですね．
（やたらスクロールしないと読めないのも面倒な感じになりますし）

[dodox86]

@K_3578さん

コメントありがとうございます。ご案内の過去質問を見ると確かにそうですね。単独で本質問を読むと早過ぎる印象は解消しませんが、あらゆる指摘をスルーして自分の要望を優先する方もまれによくいらっしゃるから、妥当とも取れます。理解しました。

[K_3578]

@dodox86さん

私もdodox86さんのコメントを見た時は同じ事を思いましたし、BeatStarさんがそこまで意図を汲んで
回答したかはわからないのでご指摘自体は真っ当だと思います。

[dodox86]

@BeatStarさん

> まだ完璧に頭が回っているわけじゃないので詳しくはわかりませんが。

えと、この文は必要でしょうか。なぜ、ご自身も認めるあやふやな状態で回答をされるのか。時に、質問内容があやふやだと回答もそうならざるを得ないこともあり、それを踏まえての文だったのかもしれませんが。

[BeatStar]

@ dodox86さん
> 無視を疑うにはさすがに急ぎ過ぎなのではないでしょうか

この質問だけなら私もそう思いますが、質問者さんの過去質問をみていると、他の方がgifファイルで修正依頼のところに載せていますが、修正された様子もなく、かと言って今回の質問に反映されているわけでもないです。

なので書きました。

とある別のユーザはそういう指摘に対して暴言を吐き、『推奨なのだからやらんくてもいいだろ。答えだけ寄越せ』的発言を繰り返している人も見かけたりします。
そういう手合いなのかなとも勘繰ったり。

[BeatStar]

@ K_3578さん
> ... この指摘は質問者に気づいて貰うためにも必要だと私は思います

まさにその意図です。

[dodox86]

@BeatStarさん
コメントありがとうございます。お気持ちは理解できます。承知しました。

[BeatStar]

@ fanaさん
> 誤記っす．一方は ')' ですね．

あ、本当ですね。(気づかなかった…)
修正します。

Answer 5

演算子の優先順位やカッコに対応した電卓はスタックを使って実装するとやりやすいと思います。
その際、計算対象の数式を逆ポーランド記法という書き方に変換することで演算子の優先順位などの煩わしさを軽減できます。

以下の記事はコードがPerlで書かれているものの、電卓のアルゴリズムについてわかりやすく解説されていますので、よければご一読ください。

日曜プログラミングで電卓を作ってみる | さくらのナレッジ

ご質問いただいたアルゴリズムが複雑でその方法で実装できるか自信がないため、質問に対する直接の回答ができず申し訳ありませんが、ご参考まで。

Comments

[fj68]

ご質問のアルゴリズムで実装できないか手元で試してみて、回答できるようになったら追記しますね。