利用栈来实现的。
/*****************************************
Copyright (c) 2015 Jingshuang Hu
@filename:demo.c
@datetime:2015.10.08
@author:HJS
@e-mail:eleftheria@163.com
@blog:http://blog.csdn.net/hujingshuang
*****************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/***********************************************/
#define MAX_LENGTH 20
/***********************************************/
typedef struct
{
char data[MAX_LENGTH];
int top;
}SqStack;
/***********************************************/
int Express_Error(char *p);//违法输入判断
SqStack Infix_suffix(char *p);//中缀转后缀
char Symbol_Priority(char ch);//优先级
int calc_suffix(SqStack p);//计算后缀表达式
char calc_two(char p1, char p2, char symbol);//两个元素之间的四则运算
void change(char *p);//转换一下
void Stack_Init(SqStack *p);//栈初始化
void Stack_Push(SqStack *p, char value);//入栈
char Stack_Pop(SqStack *p);//出栈
char Stack_Top(SqStack p);//取栈顶元素
int Stack_Length(SqStack p);//栈长
int Stack_Empty(SqStack p);//栈空
void Stack_ShowAll(SqStack p);//查看栈中元素
void Stack_Clear(SqStack *p);//清空栈
/***********************************************/
//8+(3+5-2)*2 = 20
//7+(6-1)*2+9/3 = 20
//((20/5-3)+4)*2/5 = 2
//((30-10/2)+5)/10*2/3-1 = 1
//(3+2*(12+4)/4-2)/3+2 = 5
int main()
{
int choise = 0;
char str[MAX_LENGTH];
SqStack s;
while(1)
{
printf("中缀表达式:");
gets(str);
if (Express_Error(str))//表达式不合法，重新输入
{
printf("表达是不合法，请重新输入!\n");
continue;
}
change(str);//提取字符串中的数字并凑整
s = Infix_suffix(str);//中缀转后缀
printf("后缀表达式:");
puts(s.data);
printf("结果:%d", calc_suffix(s));
getchar();getchar();
system("cls");
}
return 0;
}
/***********************************************/
void change(char *p)//转换一下
{
int i = 0, j = 0, sum = 0;
char *s = p;
while(p[i] != '\0')
{
if ((p[i] >= '0') && (p[i] <= '9'))
{
sum = sum * 10 + p[i] - '0';
if ((p[i + 1] > '9') || (p[i + 1] < '0'))
{
s[j] = sum + '0';
sum = 0;
j++;
}
}
else
{
s[j] = p[i];
j++;
}
i++;
}
s[j] = '\0';
p = s;
}
/***********************************************/
SqStack Infix_suffix(char *p)//中缀转后缀
{
char i = 0, pt = 0, pc = 0;//优先级的栈顶、当前优先级
char st = 0, sc = 0;//符号的栈顶、当前符号
SqStack s;//优先级栈、符号栈、后缀表达式栈
SqStack s1;
SqStack s2;
Stack_Init(&s);
Stack_Init(&s1);
Stack_Init(&s2);
//
while(p[i] != '\0')
{
if ((p[i] != '+') && (p[i] != '-') && (p[i] != '*') && (p[i] != '/') && (p[i] != '%') && (p[i] !='(') && (p[i] != ')'))//数字直接入栈到s2
{
Stack_Push(&s2, p[i]);
}
else//符号入栈s1，其优先级入栈s（s与s1同步）
{
pc = Symbol_Priority(p[i]);//当前优符号的先级
if (Stack_Empty(s1) || ('(' == p[i]))//s1栈空或'('则直接入栈
{
Stack_Push(&s, pc);//优先级入栈
Stack_Push(&s1, p[i]);//符号入栈
}
else
{
pt = Stack_Top(s);//优先级的栈顶
st = Stack_Top(s1);//符号的栈顶
if (')' == p[i])
{
while(st != '(')
{
Stack_Pop(&s);//优先级s出栈
Stack_Push(&s2, Stack_Pop(&s1));//符号出栈s1，并入栈到s2
st = Stack_Top(s1);
}
Stack_Pop(&s);//将'('的优先级出栈
Stack_Pop(&s1);//将'('出栈
}
else//根据优先级来判断出入栈
{
if (pc > pt)//优先级：当前符号>栈顶符号，直接入栈
{
Stack_Push(&s, pc);//优先级入栈
Stack_Push(&s1, p[i]);//符号入栈
}
else//优先级：当前符号<=栈顶符号，出栈，直到栈空或遇到'('，停止出栈
{
while((!Stack_Empty(s1)) && (Stack_Top(s1) != '(') && (Stack_Top(s) >= pc))
{
Stack_Push(&s2, Stack_Pop(&s1));
Stack_Pop(&s);
}
Stack_Push(&s1, p[i]);
Stack_Push(&s, pc);
}
}
}
}
i++;
}
while(!Stack_Empty(s1))//将s1中剩余符号出栈，并入栈到s2
{
Stack_Push(&s2, Stack_Pop(&s1));
Stack_Pop(&s);
}
Stack_Push(&s2, '\0');//入栈'\0'，搞成字符串
return s2;
}
/***********************************************/
int calc_suffix(SqStack p)//计算后缀表达式
{
int i = 0;
char *str = p.data;
char p1, p2;
SqStack s;
Stack_Init(&s);
while(str[i] != '\0')
{
if ((str[i] != '+') && (str[i] != '-') && (str[i] != '*') && (str[i] != '/') && (str[i] != '%'))//如果是数字则直接入栈
{
Stack_Push(&s, str[i]);
}
else//如果是符号，则出栈两个数字进行运算
{
p2 = Stack_Pop(&s);
p1 = Stack_Pop(&s);
Stack_Push(&s, calc_two(p1, p2, str[i]));
}
i++;
}
// Stack_Push(&s, '\0');
return (Stack_Pop(&s) - '0');//栈中最后一个数就是结果，将其出栈
}
/***********************************************/
char calc_two(char p1, char p2, char symbol)//两个元素之间的四则运算
{
char res = 0;
switch(symbol)
{
case '+':
res = (p1 - '0') + (p2 - '0');
break;
case '-':
res = (p1 - '0') - (p2 - '0');
break;
case '*':
res = (p1 - '0') * (p2 - '0');
break;
case '/':
res = (p1 - '0') / (p2 - '0');
break;
case '%':
res = (p1 - '0') % (p2 - '0');
break;
default:
break;
}
return (res + '0');
}
/***********************************************/
int Express_Error(char *p)//违法输入判断
{
int i = 0, flag = 0;
while((p[i] != '\0') && (flag == 0))
{
if (((p[i] >= '0') && (p[i] <= '9')) || ('+' == p[i]) || ('-' == p[i]) || ('*' == p[i]) || ('/' == p[i]) || ('(' == p[i]) || (')' == p[i]))
{
flag = 0;
}
else
{
flag = 1;
}
i++;
}
return flag;
}
/***********************************************/
char Symbol_Priority(char ch)//优先级
{
if (('+' == ch) || ('-' == ch))
{
return 0;
}
else if (('*' == ch) || ('/' == ch) || ('%' == ch))
{
return 1;
}
else if (('(' == ch) || (')' == ch))
{
return 2;
}
else
{
return 3;//错误代码
}
}
/***********************************************/
void Stack_Init(SqStack *p)//栈初始化
{
p->top = -1;
}
/***********************************************/
void Stack_Push(SqStack *p, char value)//入栈
{
p->top++;
p->data[p->top] = value;
}
/***********************************************/
char Stack_Pop(SqStack *p)//出栈
{
return p->data[p->top--];
}
/***********************************************/
char Stack_Top(SqStack p)//栈顶
{
return p.data[p.top];
}
/***********************************************/
int Stack_Length(SqStack p)//栈长
{
return p.top;
}
/***********************************************/
int Stack_Empty(SqStack p)//1栈空 0非空
{
return (p.top <= -1) ? 1 : 0;
}
/***********************************************/
void Stack_ShowAll(SqStack p)//查看栈中元素
{
char ch;
while(!Stack_Empty(p))
{
ch = Stack_Pop(&p);
printf("%c", ch);
}
printf("\n");
}
/***********************************************/
void Stack_Clear(SqStack *p)//清空栈
{
p->top = -1;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/hujingshuang/article/details/49679579