用栈求后缀表达式的值

题目

表达式 (3 + 4) × 2 的后缀形式是 3 4 + 2 ×.
编写 C 程序, 按所示算法, 为使用 整数操作数 及 4 种常用算数运算符 的后缀表达式求值.

算法描述:
从空栈开始, 由左至右扫描后缀表达式.
遇到操作数就将其压入栈.
遇到运算符就弹出栈两次, 对弹出的两个值应用该运算符, 将结果压入栈.
处理完成后, 结果应该留在栈中.

处理的符号操作栈
 初始化Ø
3push 33
4push 43, 4
+pop 4, pop 3Ø
计算 7 = 3 + 4
push 77
2push 27, 2
×pop 2, pop 7Ø
计算 14 = 7 × 2
push 1414

栈实现

BOOL 声明在 bool.h 中.
STACK 声明在 stack.h 中.

  1. /* bool.h */
  2.  
  3. #ifndef BOOL_H
  4. #define BOOL_H 1
  5.  
  6. typedef enum { FALSE, TRUE } BOOL;
  7.  
  8. #endif
  1. /* stack.h */
  2.  
  3. #ifndef STACK_H
  4. #define STACK_H 1
  5.  
  6. #include "bool.h"
  7.  
  8. #define MAX 256
  9. #define DefEleType(EleType, StackType) \
  10. typedef struct StackType { \
  11. EleType arr[MAX]; \
  12. int top; \
  13. } StackType
  14. DefEleType(int, STACK);
  15.  
  16. void iniStack(STACK * ps);
  17. BOOL isEmpty(STACK * ps);
  18. BOOL isFull(STACK * ps);
  19. BOOL peak(STACK * ps, int * px);
  20. BOOL pop(STACK * ps, int * px);
  21. BOOL push(int x, STACK * ps);
  22.  
  23. #endif
  1. /* stack.c */
  2.  
  3. #include "stack.h"
  4.  
  5. void iniStack(STACK * ps) {
  6. ps->top = -1;
  7. }
  8.  
  9. BOOL isEmpty(STACK * ps) {
  10. return ps->top == -1;
  11. }
  12.  
  13. BOOL isFull(STACK * ps) {
  14. return ps->top == MAX-1;
  15. }
  16.  
  17. BOOL peak(STACK * ps, int * px) {
  18. if ( isEmpty(ps) )
  19. return FALSE;
  20.  
  21. (*px) = ps->arr[ps->top];
  22. return TRUE;
  23. }
  24.  
  25. BOOL pop(STACK * ps, int * px) {
  26. if ( isEmpty(ps) )
  27. return FALSE;
  28.  
  29. (*px) = ps->arr[(ps->top)--];
  30. return TRUE;
  31. }
  32.  
  33. BOOL push(int x, STACK * ps) {
  34. if ( isFull(ps) )
  35. return FALSE;
  36.  
  37. ps->arr[++(ps->top)] = x;
  38. return TRUE;
  39. }

arith1

从终端读入表达式, 然后求值.
省略了输入检查, 异常处理等.

  1. /* arith1.c */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include "stack.h"
  7.  
  8. BOOL isOperator(const char * op) {
  9. if ( strlen(op) != 1)
  10. return FALSE;
  11.  
  12. if ( op[0] == '+' || op[0] == '-' || op[0] == '*' || op[0] == '/' )
  13. return TRUE;
  14. else
  15. return FALSE;
  16. }
  17.  
  18. int calc(int a, int b, const char * op) {
  19. switch ( op[0] ) {
  20. case '+':
  21. return a + b;
  22. case '-':
  23. return b - a;
  24. case '*':
  25. return a * b;
  26. case '/':
  27. return b / a;
  28. default:
  29. fprintf(stderr, "Error: invalid operator\n");
  30. exit(EXIT_FAILURE);
  31. }
  32. }
  33.  
  34. int main(int argc, char ** argv) {
  35. int a, b;
  36. int i;
  37. STACK s;
  38.  
  39. iniStack(&s);
  40.  
  41. for ( i = 1; i < argc; i++ ) {
  42. if ( !isOperator(argv[i]) )
  43. push((int) strtol(argv[i], NULL, 10), &s);
  44. else {
  45. pop(&s, &a);
  46. pop(&s, &b);
  47. push(calc(a, b, argv[i]), &s);
  48. }
  49. }
  50.  
  51. if ( peak(&s, &i) )
  52. printf("result: %i\n", i);
  53.  
  54. return EXIT_SUCCESS;
  55. }

编译:

  1. **$ gcc arith1.c stack.c -o arith1

注意:
对于乘号 *, 直接输入, 终端 bash 会对 * 做特殊处理, 记得在前面加转义字符 \, 有点烦.

  1. **$ ./arith1 3 4 + 2 \*
  2. result: 14

arith2

把乘号 * 换成 ×.
符号 × 超出了 ASCII 的范围, 定义成字符串, 这方法有点愚.

  1. /* arith2.c */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include "stack.h"
  7.  
  8. static char ADD[] = "+";
  9. static char SUB[] = "-";
  10. static char MUL[] = "×";
  11. static char DIV[] = "/";
  12. static char GUARD[] = "";
  13. static char * OPSET[] = { ADD, SUB, MUL, DIV, GUARD };
  14.  
  15. BOOL isOperator(const char * op);
  16. int calc(int a, int b, const char * op);
  17.  
  18. int main(int argc, char ** argv) {
  19. int a, b;
  20. int i;
  21. STACK s;
  22.  
  23. iniStack(&s);
  24.  
  25. for ( i = 1; i < argc; i++ ) {
  26. if ( !isOperator(argv[i]) )
  27. push((int)strtol(argv[i], NULL, 10), &s);
  28. else {
  29. pop(&s, &a);
  30. pop(&s, &b);
  31. push(calc(a, b, argv[i]), &s);
  32. }
  33. }
  34.  
  35. if ( peak(&s, &i) )
  36. printf("result: %i\n", i);
  37.  
  38. return EXIT_SUCCESS;
  39. }
  40.  
  41. BOOL isOperator(const char * op) {
  42. int i = 0;
  43. while ( strcmp(OPSET[i], "") ) {
  44. if ( strcmp(op, OPSET[i]) == 0 )
  45. return TRUE;
  46. i++;
  47. }
  48.  
  49. return FALSE;
  50. }
  51.  
  52. int calc(int a, int b, const char * op) {
  53. int flag = 0;
  54. while ( strcmp(OPSET[flag], op) )
  55. flag++;
  56.  
  57. switch ( flag ) {
  58. case 0:
  59. return a + b;
  60. case 1:
  61. return b - a;
  62. case 2:
  63. return a * b;
  64. case 3:
  65. return b / a;
  66. default:
  67. exit(EXIT_FAILURE);
  68. }
  69. }

编译, 运行:

  1. **$ gcc arith2.c stack.c -o arith2
  2. **$ ./arith2 3 4 + 2 ×
  3. result: 14

arith3

定义一个结构, 把 运算符 和 操作 绑定.
定义了一个 DType 类型, 想着扩展到 double 型数据的计算, 后来发现这不仅仅是换个说明符的问题, 就放弃啦.
... , 无论怎么处理除法都觉得别扭

  1. /* arith.h */
  2.  
  3. #ifndef ARITH_H
  4. #define ARITH_H 1
  5.  
  6. #include "bool.h"
  7.  
  8. typedef int DType;
  9.  
  10. typedef struct {
  11. char * tag;
  12. DType (*calc) (DType a, DType b);
  13. } OPR;
  14.  
  15. BOOL isOperator(const char * opr);
  16. BOOL isOperand(const char * opd);
  17. DType calculate(DType a, DType b, const char * op);
  18.  
  19. #endif
  1. /* arith3.c */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include "arith.h"
  7.  
  8. static DType ADD(DType a, DType b);
  9. static DType SUB(DType a, DType b);
  10. static DType MUL(DType a, DType b);
  11. static DType DIV(DType a, DType b);
  12.  
  13. static const OPR OPRSET[] = {
  14. { "+", ADD }, { "-", SUB },
  15. { "×", MUL }, { "/", DIV },
  16. { "", NULL }
  17. };
  18.  
  19. BOOL isOperator(const char * opr) {
  20. int i = 0;
  21. while ( strcmp(OPRSET[i].tag, "") ) {
  22. if ( !strcmp(OPRSET[i].tag, opr) )
  23. return TRUE;
  24. i++;
  25. }
  26.  
  27. return FALSE;
  28. }
  29.  
  30. BOOL isOperand(const char * opd) {
  31. if ( strlen(opd) == 1 ) {
  32. if ( opd[0] >= '0' && opd[0] <= '9' )
  33. return TRUE;
  34. else
  35. return FALSE;
  36. }
  37.  
  38. int i;
  39. for ( i = strlen(opd)-1; i > 0; i-- )
  40. if ( opd[i] < '0' || opd[i] > '9' )
  41. return FALSE;
  42.  
  43. if ( opd[i] == '-'
  44. || (opd[i] > '0' && opd[i] <= '9') )
  45. return TRUE;
  46.  
  47. return FALSE;
  48. }
  49.  
  50. DType calculate(DType a, DType b, const char * op) {
  51. int i = 0;
  52. while ( strcmp(OPRSET[i].tag, op) )
  53. i++;
  54.  
  55. return OPRSET[i].calc(a, b);
  56. }
  57.  
  58. static DType ADD(DType a, DType b) {
  59. return a + b;
  60. }
  61.  
  62. static DType SUB(DType a, DType b) {
  63. return b - a;
  64. }
  65.  
  66. static DType MUL(DType a, DType b) {
  67. return a * b;
  68. }
  69.  
  70. static DType DIV(DType a, DType b) {
  71. if ( a == 0 ) {
  72. fprintf(stderr, "Error: %s[%i], %s(), bad operand, %i\n",
  73. __FILE__, __LINE__, __func__, a);
  74. exit(EXIT_FAILURE);
  75. }
  76. return b / a;
  77. }
  1. /* arith_main.c */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include "bool.h"
  6. #include "stack.h"
  7. #include "arith.h"
  8.  
  9. BOOL isValid(char * s);
  10.  
  11. int main(int argc, char ** argv) {
  12. int a, b;
  13. int i;
  14. STACK s;
  15.  
  16. iniStack(&s);
  17.  
  18. for ( i = 1; i < argc; i++ ) {
  19. if ( !isValid(argv[i]) ) {
  20. fprintf(stderr, "Error: %s[%i], %s(), bad input, %s\n",
  21. __FILE__, __LINE__, __func__, argv[i]);
  22. return EXIT_FAILURE;
  23. }
  24. }
  25.  
  26. for ( i = 1; i < argc; i++ ) {
  27. if ( !isOperator(argv[i]) ) {
  28. if ( !push((int) strtol(argv[i], NULL, 10), &s)) {
  29. fprintf(stderr, "Error: %s[%i], %s(), stack overflow, %s\n",
  30. __FILE__, __LINE__, __func__, argv[i]);
  31. return EXIT_FAILURE;
  32. }
  33. }
  34. else {
  35. if ( pop(&s, &a) && pop(&s, &b) )
  36. push(calculate(a, b, argv[i]), &s);
  37. else {
  38. fprintf(stderr, "Error: %s[%i], %s(), stack underflow, %s\n",
  39. __FILE__, __LINE__, __func__, argv[i]);
  40. return EXIT_FAILURE;
  41. }
  42. }
  43. }
  44.  
  45. if ( peak(&s, &i) )
  46. printf("result: %i\n", i);
  47.  
  48. return EXIT_SUCCESS;
  49. }
  50.  
  51. BOOL isValid(char * s) {
  52. if ( isOperator(s) || isOperand(s) )
  53. return TRUE;
  54. else
  55. return FALSE;
  56. }

编译, 运行:

  1. **$ gcc arith_main.c arith3.c stack.c -o arith3
  2. **$ ./arith3 3 4 + 2 ×
  3. result: 14