利用栈实现计算表达式字符串的值（C语言）

短命女 2022-05-17 11:45 149阅读 0赞

### 利用后缀表达式的思想，输入一个字符串，计算其值。 ###

*  计算方案

#include "LinkStack.h"
    
    int priority(char ch)
    {
    	switch(ch)
    	{
    		case '(':
    			return 3;
    		case '*':
    		case '/':
    			return 2;
    		case '+':
    		case '-':
    			return 1;
    		default :
    			return 0;
    	}
    }
    
    int main()
    {
    	char opt[1024] = {0};
    	int num1 = 0, num2 = 0, i = 0, tmp = 0;
    	Stack *s_num = NULL, *s_opt = NULL;
    	
    	if(StackInit(&s_num) !=SUCCESS || StackInit(&s_opt)	!= SUCCESS)
    	{
    		printf("Stack Init Error\n");
    		return 0;
    	}
    	
    	printf("Please input:\n");
    	scanf("%s", opt);
    	
    	while(opt[i] != '\0' || StackEmpty(s_opt) != TRUE)
    	{
    		if(opt[i] >= '0' && opt[i] <= '9')
    		{
    			tmp = tmp*10 + opt[i]-'0';
    			i++;
    			if(opt[i] < '0' || opt[i] > '9')
    			{
    				Push(&s_num, tmp);
    				tmp = 0;
    			}
    		}
    		else
    		{
    			if(opt[i] == ')' && GetTop(s_opt) == '(')
    			{
    				Pop(&s_opt);
    				i++;
    				continue;
    			}
    			
    			if(StackEmpty(s_opt) == TRUE ||
    			   (GetTop(s_opt) == '(' && opt[i] != ')') ||
    			   (priority(opt[i]) > priority(GetTop(s_opt))) )
    			{
    				Push(&s_opt, opt[i]);
    				i++;
    				continue;
    			}
    			
    			if((opt[i] == '\0' && StackEmpty(s_opt) != TRUE)||
    			   (opt[i] == ')' && GetTop(s_opt) != '(') ||
    			   ( priority(opt[i]) <= priority( GetTop(s_opt) ) ) )
    			{
    				switch(Pop(&s_opt))
    				{
    					case '+':
    						num1 = Pop(&s_num);
    						num2 = Pop(&s_num);
    						Push(&s_num, num1+num2);
    						break;
    					case '-':
    						num1 = Pop(&s_num);
    						num2 = Pop(&s_num);
    						Push(&s_num, num2-num1);
    						break;
    					case '*':
    						num1 = Pop(&s_num);
    						num2 = Pop(&s_num);
    						Push(&s_num, num1*num2);
    						break;
    					case '/':
    						num1 = Pop(&s_num);
    						num2 = Pop(&s_num);
    						Push(&s_num, num2/num1);
    						break;
    				}
    			}
    		}
    	}
    	
    	printf("%d\n", GetTop(s_num));
    	return 0;
    }

*  头文件：

#ifndef _LINKSTACK_H
    #define _LINKSTACK_H
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define SUCCESS 10000
    #define FAILURE 10001
    #define TRUE    10002
    #define FALSE   10003
    
    typedef int Elemtype;
    
    typedef struct node
    {
    	Elemtype data;
    	struct node *next;
    }Node;
    
    typedef struct stack
    {
    	struct node *top;
    	int count;
    }Stack;
    
    int StackInit(Stack **stack);
    int StackEmpty(Stack *stack);
    int Push(Stack **stack, Elemtype e);
    int GetTop(Stack *stack);
    int Pop(Stack **stack);
    int StackClear(Stack **stack);
    int StackDestory(Stack **stack);
    
    #endif

*  功能函数：

#include "LinkStack.h"
    
    int StackInit(Stack **stack)
    {
    	if(NULL == stack)
    	{
    		return FAILURE;
    	}
    	
    	*stack = (Stack *)malloc(sizeof(Stack)*1);
    	if(NULL == *stack)
    	{
    		return FAILURE;
    	}
    	
    	(*stack)->top = NULL;
    	(*stack)->count = 0;
    	
    	return SUCCESS;
    }
    
    int StackEmpty(Stack *stack)
    {
    	if(NULL == stack)
    	{
    		return FAILURE;
    	}
    	
    	return (stack->top == NULL) ? TRUE : FALSE;
    }
    
    int Push(Stack **stack, Elemtype e)
    {
    	if(NULL == stack || NULL == *stack)
    	{
    		return FAILURE;
    	}
    	
    	Node *p;
    	p = (Node *)malloc(sizeof(Node));
    	if(NULL == p)
    	{
    		return FAILURE;
    	}
    	
    	p->data = e;
    	p->next = (*stack)->top;
    	(*stack)->top = p;
    	(*stack)->count++;
    
    	return SUCCESS;	
    }
    
    int GetTop(Stack *stack)
    {
    	if(NULL == stack)
    	{
    		return FAILURE;
    	}
    	
    	return stack->top->data;
    }
    
    int Pop(Stack **stack)
    {
    	if(NULL == stack || NULL == *stack)
    	{
    		return FAILURE;
    	}
    	
    	Node *p = (*stack)->top;
    	Elemtype e = (*stack)->top->data;
    	
    	(*stack)->top = (*stack)->top->next;
    	(*stack)->count--;
    	free(p);
    	p = NULL;
    	
    	return e;
    }
    
    int StackClear(Stack **stack)
    {
    	if(NULL == stack || NULL == *stack)
    	{
    		return FAILURE;
    	}
    	
    	Node *p;
    	
    	while((*stack)->top != NULL)
    	{
    		p = (*stack)->top;
    		(*stack)->top = (*stack)->top->next;
    		(*stack)->count--;
    		free(p);
    	}
    	return SUCCESS;
    }
    
    int StackDestory(Stack **stack)
    {
    	if(NULL == stack || NULL == *stack)
    	{
    		return FAILURE;
    	}
    	
    	Node *p;
    	
    	while((*stack)->top != NULL)
    	{
    		p = (*stack)->top;
    		(*stack)->top = (*stack)->top->next;
    		(*stack)->count--;
    		free(p);
    	}
    	
    	free(*stack);
    	*stack = NULL;
    	
    	return SUCCESS;
    }