表达式求值
题目描述
从键盘输入一个算术表达式并输出它的结果，算术表达式可包含加、减、乘、除、十进制整数和小括号，利用栈实现。
题目解析
本题难度较高，属于高阶题目，需要先转后缀表达式再计算，这里展示一种解法，后续学习了高阶解决方法会更新该题目，下面代码由本人进行一定程度改造所写，基本功能可以实现，如有其他bug自行解决
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 30
typedef struct my_stack
{
int a[N];
int top;
}ST;
int isempty(ST* T)
{
if (T->top < 0)
return 1;
else
return 0;
}
int isfull(ST* T)
{
if (T->top == N - 1)
return 1;
else
return 0;
}
int gettop(ST* T)
{
return T->a[T->top];
}
int pop(ST* T)
{
int x;
if (T->top < 0)
{
printf("Zhan is empty,can not pop!\n");
exit(0);
}
else
{
x = T->a[T->top];
(T->top)--;
return x;
}
}
void push(ST* T, int s)
{
if (T->top == N - 1)
{
printf("Zhan is full,can not push,you can modify N and then you can push again.\n");
exit(0);
}
else
{
(T->top)++;
T->a[T->top] = s;
}
}
void transfer(char* in, char* post)
{
ST T;
int i, j, flag = 0;
int count;
int right = 0, left = 0;
T.top = -1;
for (i = 0, j = 0; in[i] != '\0'; i++)
{
switch (in[i])
{
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
for (count = 0; (in[i] <= '9' && in[i] >= '0') || in[i] == '.'; i++, j++)
{
post[j] = in[i];
if (in[i] == '.')
count++;
}
i--;
if (count > 1)
{
printf("数中有两个小数点\n");
exit(0);
}
post[j] = ' ';
j++;
flag = 1;
break;
case '(':
if (flag)
{
printf("数字后直接跟括号\n");
exit(0);
}
push(&T, in[i]);
left++;
break;
case ')':
right++;
while (gettop(&T) != '(')
{
post[j] = pop(&T);
j++;
}
pop(&T);
break;
case '+':
case '-':
if (!flag && i != 0)
{
printf("有连续两个运算符之间没有数字\n");
exit(0);
}
while (!isempty(&T) && gettop(&T) != '(')
{
post[j] = pop(&T);
j++;
}
push(&T, in[i]);
flag = 0;
break;
case '*':
case '/':
if (!flag)
{
printf("有连续两个运算符之间没有数字\n");
exit(0);
}
while (!isempty(&T) && (gettop(&T) == '/' || gettop(&T) == '*'))
{
post[j] = pop(&T);
j++;
}
push(&T, in[i]);
flag = 0;
break;
default:
printf("输入非法字符，无法试别\n");
exit(0);
}
}
if (left != right)
{
printf("左右括号不匹配\n");
exit(0);
}
while (!isempty(&T))
{
post[j] = pop(&T);
j++;
}
post[j] = '\0';
}
float Calculate_zhong(char* post)
{
int i, j, top = -1, flag;
int len;
float temp, aa[N]={
0};
char ch[N];
for (i = 0; post[i] != '\0'; i++)
{
if (post[i] >= '0' && post[i] <= '9')
{
flag = 0;
j = 0;
while (post[i] != ' ')
{
if (post[i] == '.')
{
flag = 1;
}
ch[j] = post[i];
i++;
j++;
}
ch[j] = '\0';
if (flag)
{
for (j = 0; ch[j] != '.'; j++);
len = j - 1;
for (j = 0, temp = 0.; ch[j] != '.'; j++)
{
temp += (ch[j] - '0') * (float)pow(10, len - j);
}
for (j++, len++; ch[j] != '\0'; j++)
{
temp += (ch[j] - '0') * (float)pow(10, len - j);
}
}
else
{
for (j = 0; ch[j] != '\0'; j++);
len = j - 1;
for (j = 0, temp = 0.; ch[j] != '\0'; j++)
{
temp += (ch[j] - '0') * (float)pow(10, len - j);
}
}
top++;
aa[top] = temp;
}
else
{
switch (post[i])
{
case'+':
temp = aa[top];
top--;
temp += aa[top];
aa[top] = temp;
break;
case'-':
temp = aa[top];
top--;
temp = aa[top] - temp;
aa[top] = temp;
break;
case'*':
temp = aa[top];
top--;
temp = temp * aa[top];
aa[top] = temp;
break;
case'/':
temp = aa[top];
top--;
temp = aa[top] / temp;
aa[top] = temp;
}
}
}
return aa[top];
}
int main()
{
char zhong[N], hou[N];
float answer;
printf("需要计算的中缀表达式为:");
scanf("%s", zhong);
transfer(zhong, hou);
answer = Calculate_zhong(hou);
printf("%.2f\n", answer);
}
