A48210. 表达式求值求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。在计算机中，我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式，然后对后缀表达式求值。加、减、乘、除、乘方分别用+，-，*, /, ^来表示。表达式可以有圆括号()。输入第一行为测试数据的组数N。接下来的N行，每行是一个中缀表达式。每个表达式中，圆括号、运算符和运算数相互之间都用空格分隔，运算数是整数。一般运算数可正可负（…
填空题
困难
知识点
题目描述
表达式求值
求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。
在计算机中，我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式，然后对后缀表达式求值。
加、减、乘、除、乘方分别用+，-，*, /, ^来表示。表达式可以有圆括号()。
输入
第一行为测试数据的组数N。
接下来的N行，每行是一个中缀表达式。
每个表达式中，圆括号、运算符和运算数相互之间都用空格分隔，运算数是整数。一般运算数可正可负（负数的符号和数字之间无空格），指数一定为自然数(0和正整数)。不必考虑除0的情况。每个运算数均可由int放下。不必考虑溢出。中缀表达式的字符串长度不超过600。乘方的优先级比乘除都高，结合性是向左结合，如2 ^ 3 ^ 4表示( 2 ^ 3 ) ^ 4 = 4096。除法的商向零取整。
输出
对每一组测试数据输出一行，为表达式的值
样例输入
2
31 * ( 5 - ( -3 + 25 ) ) + 70 ^ 2
2 * 5 + 6 * ( 7 - 8 ) + 6
样例输出
4373
10
参考答案
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAXSIZE 100
int result[100], count = 0;
typedef struct
{
char* base, * top;
int stacksize;
}stack1; //存运算符号
typedef struct
{
int* base, * top;
int stacksize;
}stack2; //存数字
void Initstack1(stack1* s)
{
s->top = s->base = (char*)malloc(sizeof(char) * MAXSIZE);
s->stacksize = MAXSIZE;
}
void Initstack2(stack2* s)
{
s->top = s->base = (int*)malloc(sizeof(int) * MAXSIZE);
s->stacksize = MAXSIZE;
}
void Push1(stack1* s, char c)
{
*s->top = c;
s->top++;
}
void Push2(stack2* s, int a)
{
*s->top = a;
s->top++;
}
void Pop1(stack1* s, char* c)
{
*c = *--(s->top);
}
void Pop2(stack2* s, int* a)
{
*a = *--(s->top);
}
int stacklen1(stack1* s)
{
return(s->top - s->base);
}
int stacklen2(stack2* s)
{
return(s->top - s->base);
}
void cauclate(char* str)
{
stack1 s1;
stack2 s2;
int i, j, d, e;
char c, strtemp[20];
Initstack1(&s1);
Initstack2(&s2);
for (i = 0, j = 0;i < strlen(str);i++)
{
while (str[i] >= '0' && str[i] <= '9')
{
strtemp[j++] = str[i];
strtemp[j] = '\0';
i++;
if (str[i] < '0' || str[i] > '9')
{
Push2(&s2, atoi(strtemp)); //将数字入栈
j = 0;
break;
}
}
if (str[i] == '(')
{
Push1(&s1, str[i]);
}
else if (str[i] == ')')
{
Pop1(&s1, &c);
while ('(' != c)
{
switch (c)
{
case '+':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d + e);
break;
case '-':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d - e);
break;
case '*':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d * e);
break;
case '/':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d / e);
break;
case '^':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, pow(d, e));
break;
default:;
}
Pop1(&s1, &c);
}
}
else if (str[i] == '+')
{
if (!stacklen1(&s1))
Push1(&s1, str[i]);
else
{
do
{
Pop1(&s1, &c);
switch (c)
{
case '(':Push1(&s1, c);break;
case '+':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d + e);
break;
case '-':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d - e);
break;
case '*':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d * e);
break;
case '/':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d / e);
break;
case '^':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, pow(d, e));
break;
default:;
}
} while (stacklen1(&s1) && '(' != c);
Push1(&s1, str[i]);
}
}
else if (str[i] == '-')
{
if (str[i + 1] != ' ') //说明是负号
{
strtemp[j++] = '-';
strtemp[j] = '\0';
}
else //说明是减号
{
if (!stacklen1(&s1))
Push1(&s1, str[i]);
else
{
do
{
Pop1(&s1, &c);
switch (c)
{
case '(':Push1(&s1, c);break;
case '+':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d + e);
break;
case '-':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d - e);
break;
case '*':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d * e);
break;
case '/':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d / e);
break;
case '^':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, pow(d, e));
break;
default:;
}
} while (stacklen1(&s1) && '(' != c);
Push1(&s1, str[i]);
}
}
}
else if (str[i] == '*' || str[i] == '/')
{
if (!stacklen1(&s1))
Push1(&s1, str[i]);
else
{
do
{
Pop1(&s1, &c);
switch (c)
{
case '(':
case '+':
case '-':
Push1(&s1, c);
break;
case '*':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d * e);
break;
case '/':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d / e);
break;
case '^':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, pow(d, e));
break;
default:;
}
} while (stacklen1(&s1) && ('*' == c || '/' == c || '^' == c));
Push1(&s1, str[i]);
}
}
else if (str[i] == '^')
{
if (!stacklen1(&s1))
Push1(&s1, str[i]);
else
{
do
{
Pop1(&s1, &c);
switch (c)
{
case '(':
case '+':
case '-':
case '*':
case '/':
Push1(&s1, c);
break;
case '^':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, pow(d, e));
break;
default:;
}
} while (stacklen1(&s1) && '^' == c);
Push1(&s1, str[i]);
}
}
}
while (stacklen1(&s1))
{
Pop1(&s1, &c);
switch (c)
{
case '+':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d + e);
break;
case '-':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d - e);
break;
case '*':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d * e);
break;
case '/':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, d / e);
break;
case '^':
Pop2(&s2, &e);
Pop2(&s2, &d);
Push2(&s2, pow(d, e));
break;
default:;
}
}
Pop2(&s2, &d);
result[count++] = d;
}
int main()
{
int N;
char str[600];
int i;
scanf("%d", &N);
getchar();
for (i = 0;i < N;i++)
{
gets(str);
cauclate(str);
}
for (i = 0;i < count;i++)
printf("%d\n", result[i]);
return 0;
}答案解析
使用两个栈，stack1用于存储操作符，stack2用于存储操作数
从左往右扫描输入的字符串，遇到操作数入栈stack2，这里需要用到atoi()函数将字符串型转化为整型
操作符优先级 + = - < ***** = / < ^
遇到操作符时，如果stack1栈顶操作符优先级更高(或相同)，则出栈，并且从stack2栈中弹出两个数，进行计算，计算结果压入stack1内
操作符继续与栈顶操作符的比较优先级，若stack1栈顶操作符优先级更高(或相同)，重复上述操作；否则将操作符入栈stack1
如果遇到操作符高于栈顶操作符优先级，则直接入栈stack1
遇到左括号，直接入栈stack1；遇到右括号，则将stack1内操作符依次全部出栈并计算，直到遇到左括号
上一题
下一题