|
功能： 实现计算器，可以运算带括号的表达式。 如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] 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]) 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
#include
#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
实现效果 
|