c言語スタックの応用
2746 ワード
スタックの役割は、再帰関数を非再帰関数に変換することです.階乗にはパラメータが一つしかないので、パラメータをスタックに入ればいいです.
生活の中で使うのは似たような(9*7)+8の表現です.このような表現は中綴り式といいます.表現は観察にはいいですが、計算機の計算には不利です.
私たちは計算する時に9*7*を入力します. 8+,このような方法はサフィックス表現と呼ばれています.操作子は二つの操作数の後に付いています.括弧を使わないのが特徴です.
したがって、私たちがやるべき最初のことは、中式を拡張式に変換することです.
考え方を変えます.1.数字を読むと、数字を列に送ります.
2.オペレータに遭遇したときは、2つの数字を読むごとに、スタックから1つのオペレータをキューに送る.
3.操作符が左括弧の場合、操作符は右括弧まで読み、すべての操作符を左括弧に送ります.
拡張子式の計算:
1.キュー種が1つの数字文字に読み取られた場合、それをスタックに入れる
2.キューの中でオペレータを1つ読み取った場合、スタックから2つの操作数を読み取って計算し、結果をスタックに入れます.
3.最終的なスタックに残された唯一の要素は演算結果です.
拡張子式の計算コード(キーボードから拡張子式を入力して、拡張子式に変換します.将来はコードで実現します.次回は実現します.)
int nfact(int n)
{
int res = 1;
int temp = 1;
PSeqStack *stack = NULL;//
creatEmptyStack(&stack, n);//
// ,
while(n > 0){
push(stack, n);
n = n-1;
}
// ,
while(!isEmptyStack(*stack)){
res = res*readTop(*stack);
pop(stack, &temp);
}
return res;
}
は、スタックを用いてビット式の演算を行う.生活の中で使うのは似たような(9*7)+8の表現です.このような表現は中綴り式といいます.表現は観察にはいいですが、計算機の計算には不利です.
私たちは計算する時に9*7*を入力します. 8+,このような方法はサフィックス表現と呼ばれています.操作子は二つの操作数の後に付いています.括弧を使わないのが特徴です.
したがって、私たちがやるべき最初のことは、中式を拡張式に変換することです.
考え方を変えます.1.数字を読むと、数字を列に送ります.
2.オペレータに遭遇したときは、2つの数字を読むごとに、スタックから1つのオペレータをキューに送る.
3.操作符が左括弧の場合、操作符は右括弧まで読み、すべての操作符を左括弧に送ります.
拡張子式の計算:
1.キュー種が1つの数字文字に読み取られた場合、それをスタックに入れる
2.キューの中でオペレータを1つ読み取った場合、スタックから2つの操作数を読み取って計算し、結果をスタックに入れます.
3.最終的なスタックに残された唯一の要素は演算結果です.
拡張子式の計算コード(キーボードから拡張子式を入力して、拡張子式に変換します.将来はコードで実現します.次回は実現します.)
#include
#include
#include
typedef char USER_TYPE;
#include "stack.h"
void skipBlank(char *str);
void getdeal(char *str);
void dealalpha(char ch);
void getout();
PSeqStack *stack = NULL;
void dealalpha(char ch)// ,
{
char num1 = 0;
char num2 = 0;
char num3 = 0;
switch (ch){
case '+':pop(stack, &num1);
pop(stack, &num2);
num3 = num2+ num1;// ascii ,
//+ 96
push(stack,num3);
break;
case '-':pop(stack, &num1);
pop(stack, &num2);
num3 = num2 - num1;
push(stack,num3);
break;
case '*':pop(stack, &num1);
pop(stack, &num2);
num3 = num2 * num1;
push(stack,num3);
break;
case '/':pop(stack, &num1);
pop(stack, &num2);
num3 = num2 / num1;
push(stack,num3);
break;
}
}
void skipBlank(char *str)
{
int i = 0, j = 0;
for(i = 0; str[i];){puts("sb");
if(str[i] == ' '){//
i++;
}else{
str[j] = str[i];//
j++;//
i++;//
}
}
str[j] = 0;//
}
void getdeal(char *str)
{
char ch;
int i = 0;
while(str[i]){
ch = str[i];
if('+' == str[i]||'-' == str[i]
||'/' == str[i]||'*' == str[i]){
dealalpha(ch);
i++;
}else{
ch = str[i]-48;// ascii
push(stack,ch);
i++;
}
}
}
void getout()
{
char result = 0;
pop(stack, &result);
printf(" :%d
", result);
}
int main()
{
// PSeqStack *stack = NULL;
char str[20] = {0};
printf(" :
");
gets(str);
skipBlank(str);//
creatEmptyStack(&stack,strlen(str));
getdeal(str);
getout();
return 0;
}