【雑談】文字列の計算

[みけCAT]

例えば"2*2+2/2"という文字列があり、それを解析・計算して「5」という結果を出すように、
文字列を計算するプログラムを考えたいと思います。
いろいろな実装が考えられると思うので、みんながどんな実装をするか知りたいです。

条件
・与えられる数式の長さは「常識的な範囲」
・実数で計算する
・演算子は、^（累乗）、*（掛け算）、/（割り算）、+（足し算）、-（引き算）
・演算子の優先順位は、高い順に()→^（累乗）→*/→+-
・同じ優先順位なら累乗は右から計算、その他の演算子は左から計算する
・足りない部分は適当（適切）に決めていいです

自分はこんな感じで書きました。
追加した条件は
・式に余計な空白は入らない
・eがついた実数には対応しない
という感じです。

コード:

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cctype>
using namespace std;

//作成日　2012/5/27 

enum operator_type {
	OPERATOR_NUMBER,
	OPERATOR_ADD,
	OPERATOR_SUB,
	OPERATOR_MUL,
	OPERATOR_MINUS,
	OPERATOR_DIV,
	OPERATOR_POW,
	OPERATOR_KAKKO_START,
	OPERATOR_KAKKO_END
};

struct element_t {
	double value;
	operator_type opType;
};

int getYusendo(operator_type op,bool isLeft) {
	int yusendo=0;
	bool isLeftFirst=true;
	switch(op) {
		case OPERATOR_KAKKO_END:
			yusendo=0;
			isLeftFirst=false;
			break;
		case OPERATOR_MINUS:
			yusendo=1;
			isLeftFirst=false;
		case OPERATOR_POW:
			yusendo=2;
			isLeftFirst=false;
			break;
		case OPERATOR_MUL:
		case OPERATOR_DIV:
			yusendo=3;
			isLeftFirst=true;
			break;
		case OPERATOR_ADD:
		case OPERATOR_SUB:
			yusendo=4;
			isLeftFirst=true;
			break;
		case OPERATOR_KAKKO_START:
			yusendo=5;
			isLeftFirst=true;
			break;
		default:
			return -1;
	}
	return yusendo*10+(isLeftFirst==isLeft?0:1);
}

operator_type getOperatorType(char c,bool expectValue) {
	switch(c) {
		case '+': return OPERATOR_ADD;
		case '-': return expectValue?OPERATOR_MINUS:OPERATOR_SUB;
		case '*': return OPERATOR_MUL;
		case '/': return OPERATOR_DIV;
		case '^': return OPERATOR_POW;
		case '(': return OPERATOR_KAKKO_START;
		case ')': return OPERATOR_KAKKO_END;
		default : return OPERATOR_NUMBER;
	}
}

bool strcalc(double& result,string expression) {
	vector<element_t> reversePorland;
	stack<operator_type> operatorStack;
	stack<double> calcStack;
	bool expectValue=true;
	operator_type opType;
	for(int i=0;i<expression.length();i++) {
		opType=getOperatorType(expression[i],expectValue);
		if(opType==OPERATOR_KAKKO_END) {
			//かっこの終わり
			while(!operatorStack.empty() &&
					operatorStack.top()!=OPERATOR_KAKKO_START) {
				element_t nowElement;
				nowElement.value=0;
				nowElement.opType=operatorStack.top();
				reversePorland.push_back(nowElement);
				operatorStack.pop();
			}
			if(operatorStack.empty())return false;
			operatorStack.pop();
			expectValue=false;
		} else if(opType==OPERATOR_KAKKO_START) {
			//かっこの始まり
			operatorStack.push(OPERATOR_KAKKO_START);
			expectValue=true;
		} else if(opType!=OPERATOR_NUMBER) {
			//その他の演算子
			while(!operatorStack.empty() &&
					getYusendo(operatorStack.top(),true)<getYusendo(opType,false)) {
				element_t nowElement;
				nowElement.value=0;
				nowElement.opType=operatorStack.top();
				reversePorland.push_back(nowElement);
				operatorStack.pop();
			}
			operatorStack.push(opType);
			expectValue=true;
		} else {
			//数値
			if(!expectValue)return false;
			if(!isdigit(expression[i]) && expression[i]!='.')return false;
			int j;
			bool dotExist=false;
			for(j=i;j<expression.length();j++) {
				if(isdigit(expression[j]))continue;
				else if(expression[j]=='.') {
					if(dotExist)break; else dotExist=true;
				} else break;
			}
			element_t nowElement;
			nowElement.value=atof(expression.substr(i,j-i).c_str());
			nowElement.opType=OPERATOR_NUMBER;
			reversePorland.push_back(nowElement);
			i=j-1;
			expectValue=false;
		}
	}
	if(expectValue)return false;
	while(!operatorStack.empty()) {
		if(operatorStack.top()==OPERATOR_KAKKO_START)return false;
		element_t nowElement;
		nowElement.value=0;
		nowElement.opType=operatorStack.top();
		reversePorland.push_back(nowElement);
		operatorStack.pop();
	}
	for(int i=0;i<reversePorland.size();i++) {
		if(reversePorland[i].opType==OPERATOR_NUMBER) {
			calcStack.push(reversePorland[i].value);
		} else if(reversePorland[i].opType==OPERATOR_MINUS) {
			double now;
			if(calcStack.empty())return false;
			now=calcStack.top();
			calcStack.pop();
			calcStack.push(-now);
		} else {
			double d1,d2,next;
			if(calcStack.empty())return false;
			d2=calcStack.top();
			calcStack.pop();
			if(calcStack.empty())return false;
			d1=calcStack.top();
			calcStack.pop();
			switch(reversePorland[i].opType) {
				case OPERATOR_ADD: next=d1+d2;break;
				case OPERATOR_SUB: next=d1-d2;break;
				case OPERATOR_MUL: next=d1*d2;break;
				case OPERATOR_DIV:
					if(d2==0)return false;
					next=d1/d2;break;
				case OPERATOR_POW: next=pow(d1,d2);break;
				default: return false;
			}
			calcStack.push(next);
		}
	}
	if(calcStack.empty())return false;
	result=calcStack.top();
	calcStack.pop();
	if(!calcStack.empty())return false;
	return true;
}

//テストコード
int main(void) {
	string query;
	double result;
	while(getline(cin,query)) {
		if(strcalc(result,query))printf("%f\n",result); else puts("error");
	}
	return 0;
}

日記ともかぶりますが、よろしくお願いします。

[h2so5]

Rubyで。

コード:

while line = gets
    print eval(line.gsub('^', '**')).to_s
end

[かずま]

例えば"2*2+2/2"という文字列があり、それを解析・計算して「5」という結果を出すように、
文字列を計算するプログラムを考えたいと思います。
いろいろな実装が考えられると思うので、みんながどんな実装をするか知りたいです。

過去に何度も書いていますが、これでいかがでしょうか？

コード:

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

int c;  char *p, o[] = "+-*/^ ";

int get(void) { do c = *p++ & 0xff; while (isspace(c)); return c; }

double expr(const char *s)
{
    double v;
    if (*s)
        for (v = expr(s+2); c == s[0] || c == s[1]; )
            if (c == '+') v += expr(s+2);
            else if (c == '-') v -= expr(s+2);
            else if (c == '*') v *= expr(s+2);
            else if (c == '/') v /= expr(s+2);
            else v = pow(v, expr(s));
    else if (get() == '.' || isdigit(c)) v = strtod(p-1, &p), get();
    else if (c == '(') v = expr(o), c == ')' ? get() : (c = 1);
    else if (c == '+') v = expr(s);
    else if (c == '-') v = -expr(s);
    else v = c = 1;
    return v;
}

int expression(const char *s, double *v)
{
    p = (char *)s;
    *v = expr(o);
    return c == 0;
}

int main(void)
{
    char buf[1024];  double v;

    while (printf("> "), fgets(buf, sizeof buf, stdin) && *buf != '.')
        expression(buf, &v) ? printf("   %.15g\n", v) : puts("   error");
    return 0;
}

[beatle]

条件
・実数で計算する

この条件って凄く難しいですよね。floatやdoubleを使ってしまうと狭い範囲の有理数しか表せませんし・・・。
結局記号的に計算していくしかないんですかね。

[みけCAT]

みなさん投稿ありがとうございます。

条件
・実数で計算する

この条件って凄く難しいですよね。floatやdoubleを使ってしまうと狭い範囲の有理数しか表せませんし・・・。
結局記号的に計算していくしかないんですかね。

すいません。「実数型で計算する」という意味で取ってください。

[かずま]

Unix には、YACC(Yet Another Compiler Compiler) という構文解析プログラム生成ツールがあります。
Linux には、YACC互換の bison というコマンドあって、構文規則を記述したソース a.y を与えると、a.tab.c という Cプログラムに変換してくれます。

コード:

~/tmp$ cat a.y
%{
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#define YYSTYPE double
%}
%right '^'
%left  '+' '-'
%left  '*' '/'
%left  UNARYMINUS UNARYPLUS
%token NUM
%%
line: expr { printf("  %.15g\n", $1); }
      ;
expr:  NUM { $$ = $1; }
     | '-' expr %prec UNARYMINUS { $$ = -$2; }
     | '+' expr %prec UNARYPLUS  { $$ = $2; }
     | expr '+' expr { $$ = $1 + $3; }
     | expr '-' expr { $$ = $1 - $3; }
     | expr '*' expr { $$ = $1 * $3; }
     | expr '/' expr { $$ = $1 / $3; }
     | expr '^' expr { $$ = pow($1, $3); }
     | '(' expr ')'  { $$ = $2; }
     ;
%%
char *p;

int yylex(void)
{
    int c;
    do c = *p++ & 0xff; while (isspace(c));
    if (c == '.' || isdigit(c)) yylval = strtod(p-1, &p), c = NUM;
    return c;
}

int main(void)
{
    char buf[1024];
    while (printf("> "), fgets(p = buf, sizeof buf, stdin) && *p != '.')
        yyparse();
    return 0;
}

~/tmp$ bison a.y
~/tmp$ gcc a.tab.c -ly -lm
~/tmp$ ./a.out
> 2*2+2/2
  5
> 3+
syntax error
> 355 / 113
  3.14159292035398
> .
~/tmp$

[かずま]

Unix には、YACC(Yet Another Compiler Compiler) という構文解析プログラム生成ツールがあります。
Linux には、YACC互換の bison というコマンドあって、構文規則を記述したソース a.y を与えると、a.tab.c という Cプログラムに変換してくれます。

コード:

%right '^'
%left  '+' '-'
%left  '*' '/'

間違いがありました。次のように訂正します。

コード:

%left  '+' '-'
%left  '*' '/'
%right '^'

これで ^ が * よりも優先順位が高くなります。

[かずま]

関数と変数と代入演算子を追加してみました。変数は、a～z の 26個だけです。

コード:

#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
 
int c;  char *p, o[] = "= +-*/^ ";  double var[26];
 
int get(void) { do c = *p++ & 0xff; while (isspace(c)); return c; }

double expr(char *s)
{
    double v;  char *q;  int a;
    if (*s == '=')
        q = p, v = islower(a = get()) && get() == '=' ?
            var[a - 'a'] = expr(s) : (p = q, expr(s+2));
    else if (*s)
        for (v = expr(s+2); c == s[0] || c == s[1]; )
            if (c == '+') v += expr(s+2);
            else if (c == '-') v -= expr(s+2);
            else if (c == '*') v *= expr(s+2);
            else if (c == '/') v /= expr(s+2);
            else v = pow(v, expr(s));
    else if (get() == '.' || isdigit(c)) v = strtod(p-1, &p), get();
    else if (c == '(') v = expr(o), c == ')' ? get() : (c = 1);
    else if (c == '+') v = expr(s);
    else if (c == '-') v = -expr(s);
    else if (!memcmp(p-1, "sqrt",4)) p += 3, v = sqrt(expr(s));
    else if (!memcmp(p-1, "exp", 3)) p += 2, v = exp(expr(s));
    else if (!memcmp(p-1, "log", 3)) p += 2, v = log(expr(s));
    else if (!memcmp(p-1, "sin", 3)) p += 2, v = sin(expr(s));
    else if (!memcmp(p-1, "cos", 3)) p += 2, v = cos(expr(s));
    else if (!memcmp(p-1, "tan", 3)) p += 2, v = tan(expr(s));
    else if (!memcmp(p-1, "asin",4)) p += 3, v = asin(expr(s));
    else if (!memcmp(p-1, "acos",4)) p += 3, v = acos(expr(s));
    else if (!memcmp(p-1, "atan",4)) p += 3, v = atan(expr(s));
    else if (!memcmp(p-1, "pi", 2)) p++, v = 3.1415926535897932, get();
    else if (islower(c)) v = var[c - 'a'], get();
    else v = c = 1;
    return v;
}
 
int expression(char *s, double *v) { return p = s, *v = expr(o), !c; } 

int assign(char *s) { p = s; return islower(get()) && get() == '='; }
 
#include <stdio.h>

int main(void)
{
    char b[1024];  double v;
    while (printf("> "), fgets(b, sizeof b, stdin) && *b != '.')
        expression(b, &v) ? assign(b) || printf("   %.15g\n", v) : puts("   error");
    return 0;
}

実行結果

コード:

> sqrt(2)
   1.4142135623731
> exp(1)
   2.71828182845905
> log(1)
   0
> pi
   3.14159265358979
> sin(pi/6)
   0.5
> x = atan(1)
> x * 4
   3.14159265358979
> a = (b = 3) * (c = 7)
> a
   21
> b
   3
> c
   7
> .

[みけCAT]

>>かずまさん
おお、なんかすごいですね。

[かずま]

RPN(逆ポーランド記法: Reverse Polish Notation) に変換してから計算するとこうなります。

コード:

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

int c;  char *p, o[] = "+-*/^ ", rpn[1600], *r;  double stack[300];

int get(void) { do c = *p++ & 0xff; while (isspace(c)); return c; }

void expr(char *s)
{
    int d;
    if (*s)
        for (expr(s+2); c == s[0] || c == s[1]; )
            d = c, expr(d=='^' ? s : s + 2), *r++ = d;
    else if (get() == '.' || isdigit(c))
        r += sprintf(r, " %.16g", strtod(p-1, &p)), get();
    else if (c == '(') expr(o), c == ')' ? get() : (c = 1);
    else if (c == '+') expr(s);
    else if (c == '-') expr(s), *r++ = '_';
    else c = 1;
}

double calc(void)
{
    double *sp = stack;
    while (get())
        if (isdigit(c)) *sp++ = strtod(p-1, &p);
        else if (c == '+') sp--, sp[-1] += *sp;
        else if (c == '-') sp--, sp[-1] -= *sp;
        else if (c == '*') sp--, sp[-1] *= *sp;
        else if (c == '/') sp--, sp[-1] /= *sp;
        else if (c == '^') sp--, sp[-1] = pow(sp[-1], *sp);
        else if (c == '_') sp[-1] = -sp[-1];
    return *--sp;
}

int expression(char *s, double *v)
{
    p = s, r = rpn, expr(o), *r = 0;
    if (c) return 0;
    printf("  RPN [%s ]\n", rpn);
    p = rpn, *v = calc();
    return 1;
}

int main(void)
{
    char buf[1024];  double v;
    while (printf("> "), fgets(buf, sizeof buf, stdin) && *buf != '.')
        expression(buf, &v) ? printf("   %.15g\n", v) : puts("   error");
    return 0;
}

実行結果

コード:

> 1+2*(3-4)/5
  RPN [ 1 2 3 4-* 5/+ ]
   0.6
> 2^2^3
  RPN [ 2 2 3^^ ]
   256
> (2^2)^3
  RPN [ 2 2^ 3^ ]
   64
> .

[かずま]

ずいぶん前ですが、数式の計算をするプログラムを示しました。でも、グローバル
変数を使っているのが気になっていて、今回その問題を解消してみました。

コード:

#include <stdlib.h>  // strtod
#include <ctype.h>   // isspace, isdigit
#include <math.h>    // pow

struct input { int c; char *p; };

static const char o[] = "+-*/^ ";

static int get(struct input *i)
{
    do i->c = *i->p++ & 0xff; while (isspace(i->c));
    return i->c;
}

static double expr(struct input *i, const char *s)
{
    double v;
    if (*s)
        for (v = expr(i, s+2); i->c == s[0] || i->c == s[1]; )
            if (i->c == '+') v += expr(i, s+2);
            else if (i->c == '-') v -= expr(i, s+2);
            else if (i->c == '*') v *= expr(i, s+2);
            else if (i->c == '/') v /= expr(i, s+2);
            else v = pow(v, expr(i, s));
    else if (get(i) == '.' || isdigit(i->c)) v = strtod(i->p-1, &i->p), get(i);
    else if (i->c == '(') v = expr(i, o), i->c == ')' ? get(i) : (i->c = 1);
    else if (i->c == '+') v = expr(i, s);
    else if (i->c == '-') v = -expr(i, s);
    else v = i->c = 1;
    return v;
}

int calc(const char *s, double *v)
{
    struct input i;
    i.p = (char *)s;
    *v = expr(&i, o);
    return i.c == 0;
}

#include <stdio.h>

int main(void)
{
    char buf[1024];  double val;

    while (printf("> "), fgets(buf, sizeof buf, stdin) && *buf != '.')
        calc(buf, &val) ? printf("   %.15g\n", val) : puts("   error");
    return 0;
}