利用堆栈算法来计算数学表达式
此程序实现的功能为输入一个中缀表达式，将其转换为后缀表达式
并求出后缀表达式的值。
主要算法：
// 后缀表达式的计算过程
/**************************************************************/
/* 算法过程，顺序扫描后缀表达式，如果是操作数，则压入栈中，如果是操作符，则从栈中弹出两个操作数进
/* 行计算，结果再压入栈。
/* 扫描结束时，栈顶元素就是表达式的值
/**************************************************************/
// 中缀表达式转化为后缀表达式
/**************************************************************/
/* 从左至右依次扫描中缀表达式
/* 如果是操作数，直接输出，如果是 ( ，放入栈中
/* 如果是 ) ，则弹出栈顶元素并放入后缀表达式中，反复执行直到栈顶元素为 ( 位置，表示括号内操作完毕
/* 如果是操作符，则将该操作符和操作符栈顶元素比较
/* 如果大于栈顶元素的优先级时，则入栈
/* 如果小于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元
素的优先级小于当前操作符优先级
/* 重复上述步骤直到遇到结束符时结束，弹出栈中所有元素并放入后缀表达式中。算法结束
/**************************************************************/
代码分三个文件。SeqStack.h SeqStack.c main.c
下方分别列出
SeqStack.h
#ifndef SEQSTACK_H
#define SEQSTACK_H
struct SeqStack
{
int MAXNUM; // 栈中最大元素个数
int t; // 栈顶位置
int *s; // 栈中元素的起始位置
};
typedef struct SeqStack *PSeqStack; // 定义顺序栈类型
typedef int DataType1; // 定义第一种元素类型为int型
typedef int DataType2; // 定义第二种元素类型为char型
PSeqStack creatEmptyStack_seq(int m); // 创建空顺序表
int isEmptyStack_seq(PSeqStack pastack); // 判断一个栈是否为空
void push_seq_int(PSeqStack pastack, DataType1 x); // 进栈(int)
void push_seq_char(PSeqStack pastack, DataType2 x); // 进栈(char)
void pop_seq(PSeqStack pastack); // 删除栈顶元素
int pop_seq_return(PSeqStack pastack); // 删除栈顶元素，同时返回栈顶元素
int top_seq(PSeqStack pastack); // 当pastack所指的栈不为空栈时，求栈顶元素的值
void print_int(PSeqStack pastack); // 输出栈内元素，不影响栈的结构（int）
void print_char(PSeqStack pastack); // 输出栈内元素，不影响栈的结构（char）
#endifSeqStack.c
#include <stdio.h>
#include <stdlib.h>
#include "SeqStack.h"
#define TRUE 1
#define FALSE 0
// 创建空顺序栈
PSeqStack creatEmptyStack_seq(int m)
{
PSeqStack pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack != NULL)
{
pastack->s = (int*)malloc(sizeof(int)*m);
if (pastack->s)
{
pastack->MAXNUM = m;
pastack->t = -1;
return(pastack);
}
else
{
free(pastack);
return NULL;
}
}
else
{
printf("out of space.\n");
}
}
// 判断一个栈是否为空
int isEmptyStack_seq(PSeqStack pastack)
{
return (pastack->t == -1);
}
// 进栈(int)
void push_seq_int(PSeqStack pastack, DataType1 x)
{
if (pastack->t >= (pastack->MAXNUM-1))
// 检查是否栈满
{
printf("overflow! \n");
}
else
{
// 若不满，先修改栈顶变量
pastack->t++;
// 把元素x放到栈顶变量的位置中
pastack->s[pastack->t] = x;
}
}
// 进栈(char)
void push_seq_char(PSeqStack pastack, DataType2 x)
{
if (pastack->t >= (pastack->MAXNUM - 1))
// 检查是否栈满
{
printf("overflow! \n");
}
else
{
// 若不满，先修改栈顶变量
pastack->t++;
// 把元素x放到栈顶变量的位置中
pastack->s[pastack->t] = x;
}
}
// 删除栈顶元素
void pop_seq(PSeqStack pastack)
{
if (isEmptyStack_seq(pastack))
{
printf("Underflow! \n");
}
else
{
pastack->t = pastack->t-1;
}
}
// 删除栈顶元素，同时返回栈顶元素
int pop_seq_return(PSeqStack pastack)
{
int temp;
if (isEmptyStack_seq(pastack))
{
printf("Underflow!\n");
}
else
{
temp = pastack->s[pastack->t];
pastack->t--;
}
return temp;
}
// 当pastack所指的栈不为空栈时，求栈顶元素的值
int top_seq(PSeqStack pastack)
{
if (isEmptyStack_seq(pastack))
{
printf("It is empty");
return 0;
}
else
{
return (pastack->s[pastack->t]);
}
}
// 输出栈内元素，不影响栈的结构（int）
void print_int(PSeqStack pastack)
{
int temp, i;
if (isEmptyStack_seq(pastack))
{
printf("It is empty.\n");
}
printf("现在栈内元素为：");
for(i=0; i<=pastack->t; i++)
{
printf("%d ", pastack->s[i]);
}
printf("\n");
}
// 输出栈内元素，不影响栈的结构（char）
void print_char(PSeqStack pastack)
{
int temp, i;
if (isEmptyStack_seq(pastack))
{
printf("It is empty.\n");
}
printf("现在栈内元素为：");
for (i = 0; i <= pastack->t; i++)
{
printf("%c ", pastack->s[i]);
}
printf("\n");
}main.c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "SeqStack.h"
#define TRUE 1
#define FALSE 0
#define MAX 30
// 定义栈和数组的最大范围
char zhong[MAX] = { '\0' }, hou[MAX] = { '\0' };
// 定义中缀表达式与后缀表达式为全局变量。
//********************************************************************
// 后缀表达式的计算过程
//********************************************************************
void HouCalculate()
{
int num1, num2, num3;
int i = 0, theValue = 0, temp = 0;
char ch;
PSeqStack stack1;
stack1 = creatEmptyStack_seq(MAX);
while (hou[i] != '#')
{
ch = hou[i];
//*******************
//调试时把这段注释去掉
//printf("\n现在处理的字符是：%c\n", ch);
//print_int(stack1);
//*******************
// 判断数字，使数字存为整体
if (isdigit(ch))
{
temp = ch - '0';
while (hou[i] != '#')
{
i++;
ch = hou[i];
// 预读一位，如果为数字则继续累加
if (isdigit(ch))
{
temp = temp * 10 + (ch - '0');
// 使数字存为一个整体
}
else
// 否则视为数字结束。
{
push_seq_int(stack1, temp);
break;
}
}
}
// 判断空格，直接跳至下一位
else if (ch == ' ')
{
i++;
}
// 判断加减乘除
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
// 将第一个弹出来的数作为算术表达式中第二个操作数
num2 = pop_seq_return(stack1);
num1 = pop_seq_return(stack1);
// 根据不同标点进行不同计算
if (ch == '+')
{
num3 = num1 + num2;
}
else if (ch == '-')
{
num3 = num1 - num2;
}
else if (ch == '*')
{
num3 = num1 * num2;
}
else
{
num3 = num1 / num2;
}
// 将得到的计算结果再推回至栈中
push_seq_int(stack1, num3);
i++;
// 指针向后读一位
}
else
{
// 特殊情况备用项
if (ch != '#')
{
i++;
// 指针向后读一位
}
}
}
// 如果栈不为空，将栈中元素输出
while (!isEmptyStack_seq(stack1))
{
theValue = pop_seq_return(stack1);
}
printf("计算后缀表达式的值为： %d\n", theValue);
printf("========================\n");
}
//********************************************************************
// 中缀表达式转化为后缀表达式
//********************************************************************
void zhongToHou()
{
int num1, num2, num3;
int i = 0, j = 0, k, flag = 0;
char ch, temp;
PSeqStack stack1, stack2;
stack1 = creatEmptyStack_seq(MAX);
printf("请输入中缀表达式：（用'#'表示结束）\n");
gets(zhong);
while (zhong[i] != '#')
{
ch = zhong[i];
//*******************
//调试时把这段注释去掉
//printf("\n现在处理的字符是：%c\n", ch);
//print_char(stack1);
//*******************
// 判断数字，使数字存为整体
if (isdigit(ch))
{
hou[j++] = ch;
while (zhong[i] != '#')
{
i++;
ch = zhong[i];
// 预读一位，如果为数字则继续输出
if (isdigit(ch))
{
hou[j++] = ch;
}
else
// 否则视为数字结束。
{
hou[j++] = ' ';
break;
}
}
}
// 判断左括号
else if (ch == '(')
{
push_seq_char(stack1, ch);
// 左括号直接入栈
i++;
// 指针向后读一位
}
// 判断右括号
else if (ch == ')')
{
do
{
temp = pop_seq_return(stack1);
hou[j++] = temp;
hou[j++] = ' ';
} while (top_seq(stack1) != '(');
// 栈顶元素不为 ( 时，弹出其中元素至后缀表达式中
if (top_seq(stack1) == '(')
{
pop_seq(stack1);
// 将栈中的 ( 弹出
}
i++;
// 指针向后读一位
}
// 判断加号和减号
else if (ch == '+' || ch == '-')
{
if (isEmptyStack_seq(stack1))
// 如果栈为空，直接将符号压入。
{
push_seq_char(stack1, ch);
}
else
{
while (1)
{
if (isEmptyStack_seq(stack1))
// 考虑在弹出几个元素后，栈空的情况。所以要放在if-else结构的第一位。
{
push_seq_char(stack1, ch);
break;
}
else if (top_seq(stack1) == '+' || top_seq(stack1) == '-' || top_seq(stack1) == '*' || top_seq(stack1) == '/')
// 如果栈顶元素优先级比ch高级或与ch平级，弹出栈顶元素直到进入其他条件跳出死循环
{
temp = pop_seq_return(stack1);
hou[j++] = temp;
hou[j++] = ' ';
}
else
{
push_seq_char(stack1, ch);
break;
}
}
}
i++;
// 指针向后读一位
}
// 判断乘号和除号
else if (ch == '*' || ch == '/')
{
if (isEmptyStack_seq(stack1))
// 如果栈为空，直接将符号压入。
{
push_seq_char(stack1, ch);
}
else
{
temp = top_seq(stack1);
while (1)
{
if (isEmptyStack_seq(stack1))
// 考虑在弹出几个元素后，栈空的情况。
{
push_seq_char(stack1, ch);
break;
}
else if (top_seq(stack1) == '*' || top_seq(stack1) == '/')
// 如果栈顶元素优先级比ch高级或与ch平级，弹出栈顶元素直到进入其他条件跳出死循环
{
temp = pop_seq_return(stack1);
hou[j++] = temp;
hou[j++] = ' ';
}
else
{
push_seq_char(stack1, ch);
break;
}
}
}
i++;
// 指针向后读一位
}
else
{
// 此为误输入的情况，报错后退出程序，以保证后缀表达式的值能正确计算
if (ch != '#')
{
printf("您的输入中包含不合法字符。\n");
exit(0);
}
}
}
// 如果栈不为空，将栈中元素输出
while (!isEmptyStack_seq(stack1))
{
hou[j++] = pop_seq_return(stack1);
hou[j++] = ' ';
}
// 输出转换后的后缀表达式
printf("========================\n");
printf("转换后的后缀表达式为：\n");
printf("%s\n", hou);
printf("========================\n");
// 为后缀表达式设置终止符
i = 0;
while (hou[i] != NULL)
{
i++;
}
hou[i] = '#';
}
int main()
{
zhongToHou();
HouCalculate();
return 0;
}部分运行结果截图： 
最新回复 [0]