博客

功能：

实现计算器，可以运算带括号的表达式。

如1+（1+1）*2+1

首先，我们需要了解中缀表达式和后缀表达式。

中缀表达式（符号在中间）：

如1+（1+1）*2+1

后缀表达式（符号在后面）：

如上会得到1 1 1 + 2 * + 1 +

步骤：


①从左往右，若遇到数字先放一边，遇到符号就进栈。

②若栈顶是“（”，接下来符号肯定进栈；若接下来遇到“）”，“）”不进栈，将符号从栈里取出，直到遇到“）”，将“）”删除。若接下来符号优先级比栈顶高则进栈，若低则取出栈顶，新符号进栈。

③将栈内最后符号出栈后，这个表达式就是后缀表达式。

④接下来从左往右遇到数字就进栈，遇到符号则将栈顶和栈顶下一个元素进行该符号运算，后出来的运算前一个，得值再进栈。

⑤最后栈内元素就是数值大小。

图例：

为了方便快速计算，我们使用两个栈。



运算数：

直接进栈

运算符：

进栈

空栈 || 优先级高 || 栈顶是“（”并且表达式不是“）”

出栈不计算

栈顶是“（”同时是表达式是“）”

出栈计算

表达式优先级不高于栈顶 || 表达式是“）”同时栈顶不是“（” || 表达式为空但是栈不为空

计算

1 * (1 + 1 ) * 2+1 * 2



main.c

/*
程序功能：实现计算器，可以运算带括号的表达式。
编程环境：Dev-C++
程序模块：main.c/linkstack.c/linkstack.h
*/
#include "linkstack.h"

int Priority(char ch)
{
	switch(ch)
	{
		case '(':
			return 3;
		case '*':
			return 2;
		case '/':
			return 2;
		case '+':
			return 1;
		case '-':
			return 1;
		default:
			return 0;
	}
}

int main()
{
	Stack s_num,s_opt;	//定义数字栈、符号栈  
	
	if (InitStack(&s_num) == FAILURE || InitStack(&s_opt) == FAILURE)
	{
		printf("初始化失败！\n");
		return -1;
	}
	
	char opt[128] = {0};
	int i = 0, tmp = 0, num1, num2;
	
	printf("请输入表达式:\n");
	scanf("%s", opt);
	
	while (opt[i] != '\0' || EmptyStack(&s_opt) != SUCCESS) //表达式不为空或栈不为空就继续 
	{
		if (opt[i] >= '0' && opt[i] <= '9')	//若下位是数字，求出asc码 
		{
			tmp = opt[i] - '0';
			i++;
			if (opt[i] < '0' || opt[i] > '9')	//若下位不是数字，将tmp入栈；若下位是数字继续循环 
			{
				push(&s_num, tmp);
				tmp = 0;
			}
		}
		else	//操作符 
		{
			if (EmptyStack(&s_opt) == SUCCESS || Priority(opt[i]) > Priority(GetTop(&s_opt)) ||
				(GetTop(&s_opt) == '(') && (opt[i] != ')'))
			{
				push(&s_opt, opt[i]);
				i++;
				continue;	
			}
			
			if (GetTop(&s_opt) == '(' && opt[i] == ')')  
			{
				pop(&s_opt);
				i++;
				continue;
			}
			
			//此处可直接用else判断 
			if (Priority(opt[i]) <= Priority(GetTop(&s_opt)) || ((opt[i] == ')') && GetTop(&s_opt) != ')') ||
				opt[i] == '\0' && EmptyStack(&s_opt) != SUCCESS)
			{
				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;
}

linkstack.c

#include "linkstack.h"

int InitStack(Stack *s)
{
	if (NULL == s)
	{
		return FAILURE;
	}
	
	s->top = NULL;
	s->length = 0;	//表示空栈 
	
	return SUCCESS;
}

int push(Stack *s, int num)
{
	if (NULL == s)
	{
		return FAILURE;
	}
	
	Node *n = (Node *)malloc(sizeof(Node) * 1);
	if (NULL == n)
	{
		return FAILURE;
	}
	
	n->data = num;
	n->next = s->top;
	s->top = n;	//更新栈顶指针 
	s->length++;
	
	return SUCCESS;
}

int GetTop(Stack *s)
{
	if (NULL == s)
	{
		return FAILURE;
	}
	
	if (s->top == NULL)
	{
		return FAILURE;
	}
	
	return s->top->data;
}

int pop(Stack *s)
{
	if (NULL == s)
	{
		return FAILURE;
	}
	
	if (s->top == NULL)	//空栈不能出栈 
	{
		return FAILURE;
	}
	
	Node *n = s->top;
	int data = n->data;
	s->top = n->next;
	free(n);
	s->length--;

	return data;
}

int EmptyStack(Stack *s)
{
	if (NULL == s)
	{
		return FAILURE;
	}
	
	return (s->top == NULL) ? SUCCESS : FAILURE;
}

linkstack.h

#ifndef LINKSTACK_H
#define LINKSTACK_H

#include <stdio.h> 
#include <stdlib.h>

#define SUCCESS 1000
#define FAILURE 1001

struct Node	//表示结点信息 
{
	int data;
	struct Node *next;
};
typedef struct Node Node;

struct Stack	//表示栈信息 
{
	Node *top;
	int length;
};
typedef struct Stack Stack;

int InitStack(Stack *stack);
int push(Stack *s, int num);
int GetTop(Stack *s);
int pop(Stack *s);
int EmptyStack(Stack *s);
 
#endif

实现效果