Seven Day栈的运用-表达式求值

完成整数表达式求值 例如：1+(2*6)/2+9-1 = ？

思路：

处理问题：

1.运算符优先级

int map(char tempChar) {//划分优先级 
	if(tempChar == '+' || tempChar =='-') return 1;
	else return 2; 
}

2.数字与符号分开处理

建立俩个栈分别存储

3.多位整数的处理

if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < sizeS(s) && isdigit(s[j]))
                x = x * 10 + s[j ++ ] - '0';
            i = j - 1;
            pushInt(num, x);
        }

实现核心：栈

---本代码是将老师发的C++代码改为C，其他的并未改动。

代码：

不支持表达式有空格

#include 
#include 

#define STACK_MAX_SIZE 20




//创建栈 char类 
typedef struct Stack {
	int top;
	int data[STACK_MAX_SIZE];//The maximum length is fixed.
}*CharStackPtr, *IntStackPtr;



 
 //初始化 
IntStackPtr intStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(Stack));
	resultPtr->top = -1;
	
	return resultPtr;
} 

CharStackPtr charStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(Stack));
	resultPtr->top = -1;
	
	return resultPtr;
}

CharStackPtr op = charStackInit();
IntStackPtr num = intStackInit();

void outputStackC(CharStackPtr paraStack) {
	if ( paraStack->top == -1) {
		printf("The stack is empty！n");
		return; 
	}
	for (int i = 0; i <=paraStack->top; i++) {
		printf("%c ", paraStack->data[i]);
	}//Of for i
	printf("rn");
}

void outputStackI(CharStackPtr paraStack) {
	if ( paraStack->top == -1) {
		printf("The stack is empty！n");
		return; 
	}
	for (int i = 0; i <=paraStack->top; i++) {
		printf("%d ", paraStack->data[i]);
	}//Of for i
	printf("rn");
}

//入栈 
void pushChar(CharStackPtr paraStackPtr, int paraValue) {
	//Step 1.Space check.
	if (paraStackPtr->top >= STACK_MAX_SIZE) {
		printf("Cannot push element: stack is fulln");
		return;
	}
	//Step 2.Updata the top.
	paraStackPtr->top++;
	//Step 3.Push element.
	paraStackPtr->data[paraStackPtr->top] = paraValue;
}

void pushInt(IntStackPtr paraStackPtr, int paraValue) {
	//Step 1.Space check.
	if (paraStackPtr->top >= STACK_MAX_SIZE) {
		printf("Cannot push element: stack is fulln");
		return;
	}
	//Step 2.Updata the top.
	paraStackPtr->top++;
	//Step 3.Push element.
	paraStackPtr->data[paraStackPtr->top] = paraValue;
}

//出栈 
void popChar(CharStackPtr paraStackPtr) {
	//Step 1.Space check.
	if(paraStackPtr->top < 0){
		printf("Cannot pop element: stack empty.n");
		return;
	}
	//Step 2.Update the top.
	paraStackPtr->top--; 
}

void popInt(IntStackPtr paraStackPtr) {
	//Step 1.Space check.
	if(paraStackPtr->top < 0){
		printf("Cannot pop element: stack empty.n");
		return;
	}
	//Step 2.Update the top.
	paraStackPtr->top--; 
}

char topChar(CharStackPtr paraStackPtr) {
	//Step 1.Space check.
	if(paraStackPtr->top < 0){
		printf("Cannot pop element: stack empty.n");
		return '';
	}
	//Step 2.Push element.
	return paraStackPtr->data[paraStackPtr->top];
}

int topInt(IntStackPtr paraStackPtr) {
	//Step 1.Space check.
	if(paraStackPtr->top < 0){
		printf("Cannot pop element: stack empty.n");
		return '';
	}
	//Step 2.Push element.
	return paraStackPtr->data[paraStackPtr->top];
}



void eval()//计算 
{
    int b = topInt(num);
    popInt(num);
    int a = topInt(num);
    popInt(num);
    char c = topChar(op);
    popChar(op);
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    pushInt(num, x);
}


int map(char tempChar) {//划分优先级 
	if(tempChar == '+' || tempChar =='-') return 1;
	else return 2; 
}

int isdigit(char tempChar) {//判断是否为数字 
	if(tempChar == '0' || tempChar == '1' || tempChar == '2'  || tempChar == '3'  || tempChar == '4' || tempChar == '5' || tempChar == '6' || tempChar == '7' || tempChar == '8' || tempChar == '9') {
		return 1;
	} else {
		return 0;
	}
}

int sizeS(char tempChar[]) {//计算表达式长度 
	int i = 0;
	while(tempChar[i] != ''){
		i++;
	}
	return i;
}

int main()
{
	char s[100] = "((4*5+6)/2+4/2)*3" ;
	
	for (int i = 0; i < sizeS(s); i ++ )
    {
        char c = s[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < sizeS(s) && isdigit(s[j]))
                x = x * 10 + s[j ++ ] - '0';
            i = j - 1;
            pushInt(num, x);
        }
        else if (c == '(') pushChar(op, c);
        else if (c == ')')
        {
            while (topChar(op) != '(') eval();
            popChar(op);
        }
        else
        {
            while (op->top != -1 && topChar(op) != '(' && map(topChar(op)) >= map(c)) eval();
            pushChar(op, c);
        }
    }
    while (op->top != -1) eval();
    outputStackI(num);
	return 0;
 }