分享：中缀表达式转后缀表达式
写的一个简单的计算器，能简单+ - * / ^ 运算，没有考虑计算结果溢出问题。处理了负号运算，合法的负号。只能是第一个数为负数，左括号开头的第一个数为负数，以及括号括起来的负数。
希望各位大牛指点下哪里不足。
程序代码：
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#define MAXSIZE 10000
struct Stackop
{
char op[MAXSIZE];
int top;
}Stackop;
struct Stacknum
{
double num[MAXSIZE];
int top;
}Stacknum;
int GetLevel(char op) //得到运算符优先级
{
if (op == '+' || op == '-')
return 1;
else if (op == '*' || op == '/')
return 2;
else if (op == '^')
return 3;
else
return -1;
}
double Caclulate(double a, double b, char symbol, int *flag)
{
switch (symbol) //数据运算，以及除数不能为0
{
case '+' :
return a + b;
case '-' :
return a - b;
case '*' :
return a * b;
case '/':
if (b == 0)
*flag = 0;
else
return a / b;
break;
case '^' :
return pow(a, b);
default :
*flag = 0;
break;
}
return 0;
}
int GetRpn(char *calc, char *rpn) //中缀表达式转后缀表达式
{
int len, i, flag, cnt, error;
error = flag = cnt = 0;
Stackop.top = -1; //字符栈为空
len = strlen(calc);
if (calc[len - 1] == '=') //考虑最后是否为=
calc[len - 1] = '\0';
for (i = 0; calc[i] != '\0'; i++) //将负数和－号区别，负数用！代替
if (calc[0] == '-' || calc[i] == '-' && calc[i - 1] == '(')
calc[i] = '!';
for (i = 0; calc[i] != '\0'; i++)
{
if (isdigit(calc[i]) || calc[i] == '!') //数字处理过程，如果扫描到的是数字，直接加入到后缀数组中
{
if (!isdigit(calc[i]))
{
i++;
flag = 1;
}
if (!isdigit(calc[i]))
return 0;
while (isdigit(calc[i]))
{
rpn[cnt++] = calc[i];
i++;
}
if (calc[i] == '.') {
rpn[cnt++] = calc[i];
++i;
while (isdigit(calc[i]))
{
rpn[cnt++] = calc[i];
i++;
}
}
if (flag)
{
rpn[cnt++] = '#'; //如果是负数末尾加#加！，表示一个负数结束
rpn[cnt++] = '!';
flag = 0;
}
else
{
rpn[cnt++] = '#'; //当是整数末尾加#，表示一个正数结束
}
}
if (calc[i] == '\0')
break;
if (calc[i] == '(') //如果是左括号直接进符号栈
Stackop.op[++Stackop.top] = calc[i];
else if (calc[i] == ')') { //当匹配到右括号出栈
while (Stackop.op[Stackop.top] != '(') //如果栈顶是左括号，直接结束，相当于空括号
{
rpn[cnt++] = Stackop.op[Stackop.top]; //挨个把括号里面的运算符转换到后缀数组中
--Stackop.top;
}
--Stackop.top; //把匹配到的左括号出栈
}
else if (Stackop.op[Stackop.top] != -1 && GetLevel(calc[i]) <= GetLevel(Stackop.op[Stackop.top]))
{ //扫描到的运算符如果比栈顶优先级低，栈里所有优先级低于扫描到运算符优先级的运算符
//加入到后缀数组
while (Stackop.op[Stackop.top] != -1 && (error = GetLevel(calc[i])) <= GetLevel(Stackop.op[Stackop.top]))
{
if (error == -1)
return 0;
rpn[cnt++] = Stackop.op[Stackop.top];
Stackop.top--;
}
Stackop.op[++Stackop.top] = calc[i]; //如果符号栈为空，或者栈里优先级大于扫描到的字符优先级，把扫描到的运算符加入字符栈
}
else
Stackop.op[++Stackop.top] = calc[i]; //字符栈空或者优先级比扫描到的运算符优先级大， 假如到字符栈
}
while (Stackop.top != -1) {
rpn[cnt++] = Stackop.op[Stackop.top]; //到最后字符栈还有运算符，一次加入到后缀数组，最后得到后缀表达式
Stackop.top--;
}
rpn[cnt] = '\0';
return 1;
}
int GetAns(char *rpn, double *result)
{
int i, flag = 1;
double num, cnt;
double a, b, val;
Stacknum.top = -1; //这里开始就是后缀表达式计算过程
for (i = 0; rpn[i] != '\0'; i++) //到这里就是入栈和出栈的过程，只要是数字就直接入栈；是字符，数字栈出栈两个元素进行运算后入栈
{ //反复此过程，到最后栈顶元素就只有一个，就是我们要的计算结果
if (rpn[i] >= '0' && rpn[i] <= '9') {
num = 0;
cnt = 1.0;
while (rpn[i] != '#' && rpn[i] != '.')
{
num = num * 10.0 + (rpn[i] - '0');
i++;
}
if (rpn[i] == '.')
{
i++;
while (rpn[i] != '#')
{
num = num * 10.0 + (rpn[i] - '0');
cnt *= 10;
i++;
}
}
if (rpn[i + 1] == '!')
{
i++;
Stacknum.num[++Stacknum.top] = num / cnt * (-1); //字符串转换为数字或者浮点数入数字栈
}
else
Stacknum.num[++Stacknum.top] = num / cnt;
}
else
{ //匹配到运算符，两个数字出栈参加运算再进栈
b = Stacknum.num[Stacknum.top--];
if (Stacknum.top == -1)
return 0;
a = Stacknum.num[Stacknum.top--];
val = Caclulate(a, b, rpn[i], &flag);
Stacknum.num[++Stacknum.top] = val;
}
}
*result = Stacknum.num[Stacknum.top];
if(!flag)
return 0;
return 1;
}
int main()
{
char calc[MAXSIZE], rpn[MAXSIZE];
double result;
while (1)
{
printf("Please input calculate expression and expression can't hava special symbols!\n\n");
scanf("%[^\n]%*c", calc); //表示读一行，解决scanf不能读空格的问题
if (!GetRpn(calc, rpn))
{
printf("\nError: expresion error!\n");
continue;
}
if (GetAns(rpn, &result))
printf("\nCalculate val = %lf\n\n", result);
else
printf("\nError: expresion error!\n");
}
return 0;
}[此贴子已经被作者于2017-5-28 09:42编辑过]
