電卓のアルゴリズム
学校の友達が卒論で電卓について研究するらしい。
ちょっと相談をうけたので考えてみた。。。
Now thinking...
よくサンプルソースで見るのは再帰で何をやってるのかよくわからないやつｗ
あれは未だに私も理解できないので，
中間記法 --> 逆ポーラント記法 --> 逆ポーラント電卓 --> 答え
というちょっと面倒だけどわかりやすいものにしてみました[にこっ/]
103行かぁ。。。結構長いなぁ
#include ＜stdio.h＞
#include ＜stdlib.h＞
#include ＜string.h＞
#include ＜ctype.h＞
#define STACK_SIZE 1024
#define BUFF_SIZE 1024
static stack[STACK_SIZE],
sp;
#define isop(c) (c == '+' || c == '-' || c == '*' || c == '/')
int pop (void) { if ( !sp ) exit(-1); return stack[--sp]; }
void push (int n) { if ( sp == STACK_SIZE ) exit(-1); stack[sp++] = n; }
unsigned char *mk_rpn (const unsigned char *exp);
int rpn_calc(const char *exp);
int main(void)
{
unsigned char exp[BUFF_SIZE], *rpn_exp;
for ( ; ; ) {
fprintf(stdout, ">> ");
fgets(exp, BUFF_SIZE, stdin);
exp[strlen(exp)-1] = '\0';
if ( !exp[0] ) break;
fprintf(stdout, "Your expression : %s\n\n\n", exp);
fprintf(stdout, "RPN expression : %s\n\n\n", rpn_exp = mk_rpn(exp));
fprintf(stdout, "Ans : %d\n\n\n", rpn_calc(rpn_exp));
free(rpn_exp);
}
return 0;
}
unsigned char *mk_rpn(const unsigned char *exp)
{
const int OP_PRI[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 1, 0, 2};
int i, j, l, x, y;
unsigned char *q;
sp = 0;
q = (unsigned char *)calloc(1, (l = strlen(exp))+1);
for ( i = 0, j = 0; i < l; i++ ) {
if ( isdigit(exp[i]) )
q[j++] = exp[i];
else if ( isop(exp[i]) ) {
if ( !sp )
push(exp[i]);
else if ( OP_PRI[stack[sp-1]] < OP_PRI[exp[i]] )
push(exp[i]);
else {
q[j++] = pop();
--i;
}
}
}
while ( sp )
q[j++] = pop();
q[j] = '\0';
return q;
}
int rpn_calc(const char *rpn_exp)
{
int i, x, y, l;
sp = 0;
l = strlen(rpn_exp);
for ( i = 0; i < l; i++ ) {
if ( isdigit(rpn_exp[i]) ) {
push(rpn_exp[i]-'0');
}
else {
switch ( rpn_exp[i] ) {
case '*' : push(pop()*pop()); break;
case '+' : push(pop()+pop()); break;
case '-' : x = pop(), y = pop(), push(y-x);break;
case '/' : x = pop(), y = pop(), push(y/x);break;
default : exit(-1);
}
}
}
return pop();
}
しかも39: const int OP_PRI[] とか自分らしいというか応用が利かないというか。
まぁ動くしこれを元に自分で考えてもらうことにします〜[ウィンク/]
