c言語スタックの応用

2746 ワード

スタックの役割は、再帰関数を非再帰関数に変換することです.階乗にはパラメータが一つしかないので、パラメータをスタックに入ればいいです.
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; }