表达式
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的栈顶元素。