表达式
Time Limit: 1000MS Memory limit: 65536K
题目描述
算术表达式的求值我们在小学的时候就已经熟练掌握了。给出若干个只含加减乘的表达式你的任务是计算出结果。为了简化计算，给定的表达式的运算符只包含 ‘+’、‘-’、‘*’。运算符优先级为‘*’ ＞ ‘＋’ = ‘-’。
输入
输入数据的第一行为一个正整数 T (T <= 100)，表示有 T 组测试数据。 对于每组测试数据，输入一行表达式，由数字、运算符组成，且数字和运算符之间没有空格。数字均为整数, 运算符为 ‘+’,‘ –’,‘*’ 中的一个，表达式字符串长度<=100。 数字保证没有前导0，任意两个数字之间有且仅有一个运算符（不会出现3--2 等情况），运算中间结果及最终结果保证在int范围内。
输出
对于每组测试数据，输出表达式的结果。
示例输入
1
1-2*3
示例输出
-5
01.#include<stdio.h>
02.#include<
string.h>
03.
struct
04.{
05.
char data[
110];
06.
int top;
07.}op;
08.
struct
09.{
10.
int data[
110];
11.
int top;
12.}st;
13.
void trans(
char exp[],
char postexp[])
14.{
15.
char ch;
16.
int i=
0,j=
0;
17. op.top=-
1;
18. ch=exp[i++
];
19.
20.
while(ch!=
'\0')
21. {
22.
switch(ch)
23. {
24.
case '(': op.top++; op.data[op.top]=
ch;
25.
break;
26.
case ')':
27.
while(op.data[op.top]!=
'(')
28. {
29. postexp[j]=
op.data[op.top];
30. j++;op.top--
;
31. }
32. op.top--
;
33.
break;
34.
case '+':
35.
case '-':
36.
while(op.top!=-
1&&op.data[op.top]!=
'(')
37. {
38. postexp[j]=
op.data[op.top];
39. j++; op.top--
;
40. }
41. op.top++
;
42. op.data[op.top]=
ch;
43.
break;
44.
case '*':
45.
case '/':
46.
while(op.top!=-
1&&op.data[op.top]!=
'('&&(op.data[op.top]==
'*'||op.data[op.top]==
'/'))
47. {
48. postexp[j]=
op.data[op.top];
49. j++; op.top--
;
50. }
51. op.top++
;
52. op.data[op.top]=
ch;
53.
break;
54.
default:
55.
while(ch>=
'0'&&ch<=
'9')
56. {
57. postexp[j]=ch; j++
;
58. ch=exp[i];i++
;
59. }
60. i--
;
61. postexp[j]=
'#';j++
;
62. }
63. ch=exp[i++
];
64. }
65.
while(op.top!=-
1)
66. {
67. postexp[j]=
op.data[op.top];
68. j++; op.top--
;
69. }
70. postexp[j]=
'\0';
71.}
72.
int compvalue(
char postexp[])
73.{
74.
int d;
75.
char ch;
76.
int i=
0;
77. st.top=-
1;
78. ch=postexp[i];i++
;
79.
while(ch!=
'\0')
80. {
81.
switch(ch)
82. {
83.
case '+':st.data[st.top-
1]=st.data[st.top-
1]+
st.data[st.top];
84. st.top--;
break;
85.
case '-':st.data[st.top-
1]=st.data[st.top-
1]-
st.data[st.top];
86. st.top--;
break;
87.
case '*':st.data[st.top-
1]=st.data[st.top-
1]*
st.data[st.top];
88. st.top--;
break;
89.
default:
90. d=
0;
91.
while(ch>=
'0'&&ch<=
'9')
92. {
93. d=
10*d+ch-
'0';
94. ch=postexp[i];i++
;
95. }
96. st.top++
;
97. st.data[st.top]=
d;
98. }
99. ch=postexp[i];i++
;
100. }
101.
return st.data[st.top];
102.}
103.
int main ()
104.{
105.
int t,sum;
106.
char exp[
110],postexp[
110];
107. scanf(
"%d%*c",&
t);
108.
while(t--
)
109. {
110. scanf(
"%s",exp);
111. trans( exp, postexp);
112. sum=
compvalue( postexp);
113. printf(
"%d\n",sum);
114. }
115.
return 0;
116.}
117.
118.
119.
120.
计算表达式，先将表达式转换成后缀式，再计算后缀式的值。exp存放输入的字符串，postexp存放后缀表达式，定义结构体op,
作为运算符栈。将运算符按规则进栈或出栈，若是'('直接进栈，若是')'则将左右括号之间的全部运算符出栈进入postexp数组中，
并将左括号删除，当运算符优先级不大于op运算符栈中的栈顶元素的优先级时，则依次出栈放入postexp中并将该运算符进栈。当exp
扫描完毕，把op中的元素全部出栈并放到postexp中。计算结果时，再定义结构体st存放每次计算的结果，最后输出st的栈顶元素。
转载于:https://www.cnblogs.com/LK1994/archive/2013/03/15/2962376.html
