c语言前缀表达式算结果栈相关

img


题目要求使用前缀表达式算结果 但是我只能算出来第一个 第二个好像是因为有一个两位数然后没法这样遍历 想问一下有什么修改方法吗


int pre(char* prefix) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    char y = '0';
    char* x = &y;
    int len = strlen(prefix);
    CreateStack(stack, len-1);
    int result=0;
    printf("length is %d\n", len);
    //printf("%c", prefix[0]);
    for (int i = len - 1; i >= 0; i = i - 2) {
            if (prefix[i] >= '0' && prefix[i] <= '9') {
                Push2(stack, int(prefix[i]) - 48);
                //printf("put %c in succesfully\n", prefix[i] );
            }
            else if (prefix[i] == '+') {
                int a = stack->values[stack->top];
                int b = stack->values[--stack->top];
                result = a + b;
                Pop(stack, x);
                Push2(stack, result);
            }
            else if (prefix[i] == '-') {
                int a = stack->values[stack->top];
                int b = stack->values[--stack->top];
                result = a - b;
                Pop(stack, x);
                Push2(stack, result);
            }
            else if (prefix[i] == '*') {
                int a = stack->values[stack->top];
                int b = stack->values[--stack->top];
                result = a * b;
                Pop(stack, x);
                Push2(stack, result);
            }
            else if (prefix[i] == '/') {
                int a = stack->values[stack->top];
                int b = stack->values[--stack->top];
                result = a / b;
                Pop(stack, x);
                Push2(stack, result);
            }
        }
        return result;

}

#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEFAULT_CAPICITY 20
#define CAPICITY_INC_STEP 5
#define MAX_SIZE 200

typedef struct Stack_ {
  int *data;
  int capicity;
  int top;
} Stack;

Stack *create_stack() {
  Stack *stack = (Stack *)malloc(sizeof(Stack));
  stack->data = (int *)malloc(DEFAULT_CAPICITY * sizeof(int));
  stack->capicity = DEFAULT_CAPICITY;
  stack->top = 0;
  return stack;
}

void destroy_stack(Stack *stack) {
  free(stack->data);
  free(stack);
}

int is_empty(const Stack *stack) { return stack->top == 0; }

void push_stack(Stack *stack, int value) {
  if (stack->top == stack->capicity) {
    stack->capicity += CAPICITY_INC_STEP;
    stack->data = (int *)realloc(stack->data, stack->capicity);
  }
  stack->data[stack->top++] = value;
}

int pop_stack(Stack *stack) {
  assert(stack->top > 0);
  return stack->data[--stack->top];
}

int calculate(int a, char op, int b) {
  switch (op) {
  case '+':
    return a + b;
  case '-':
    return a - b;
  case '*':
    return a * b;
  case '/':
    return a / b;
  }
  return 0;
}

int prefixEval(char *str) {
  Stack *num_stack = create_stack();
  char *tokens[MAX_SIZE];
  char *token = strtok(str, " ");
  int n = 0;
  while (token) {
    tokens[n++] = token;
    token = strtok(NULL, " ");
  }
  for (int i = n - 1; i >= 0; i--) {
    if (isdigit(*tokens[i])) {
      push_stack(num_stack, atoi(tokens[i]));
    } else {
      int a = pop_stack(num_stack);
      int b = pop_stack(num_stack);
      char op = *tokens[i];
      push_stack(num_stack, calculate(a, op, b));
    }
  }
  int res = pop_stack(num_stack);
  destroy_stack(num_stack);
  return res;
}

int main() {
  char str1[] = "- + 8 / 6 3 2";
  char str2[] = "/ + 2 10 - 9 6";
  printf("Result of str1: %d\n", prefixEval(str1));
  printf("Result of str2: %d\n", prefixEval(str2));
  return 0;
}

$ gcc -Wall main.c
$ ./a.out
Result of str1: 8
Result of str2: 4

11到15行读取数字的改一下

if (prefix[i] >= '0' && prefix[i] <= '9') {
                int tem = int(prefix[i]) - 48;
                if(prefix[i+1] >= '0' && prefix[i+1] <= '9')
                {
                    tem*=10;
                    tem+=prefix[i+1];
                    i++;
                }
                Push2(stack, tem);
                //printf("put %c in succesfully\n", prefix[i] );
            }

只是在原代码上改了一点, 分割开了字符串
strtok()需要包含string.h 
atoi()需要包含stdlib.h

```c
int pre(char* prefix) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    char y = '0';
    char* x = &y;
    int len = strlen(prefix);
    CreateStack(stack, len-1);
    int result=0, index = 0;
    char* p;
    p = NULL;
    p = strtok(prefix, " ");
    while (p){
        prefix[index] = p;
        ++ index;
        p = strtok(NULL," ");
    }
    printf("length is %d\n", len);
    //printf("%c", prefix[0]);
    for (int i = len - 1; i >= 0; i = i - 2) {
            // if (prefix[i] >= '0' && prefix[i] <= '9') {
            //     Push2(stack, int(prefix[i]) - 48);
            //     //printf("put %c in succesfully\n", prefix[i] );
            // }
            if (prefix[i] == '+') {
                int a = stack->values[stack->top];
                int b = stack->values[--stack->top];
                result = a + b;
                Pop(stack, x);
                Push2(stack, result);
            }
            else if (prefix[i] == '-') {
                int a = stack->values[stack->top];
                int b = stack->values[--stack->top];
                result = a - b;
                Pop(stack, x);
                Push2(stack, result);
            }
            else if (prefix[i] == '*') {
                int a = stack->values[stack->top];
                int b = stack->values[--stack->top];
                result = a * b;
                Pop(stack, x);
                Push2(stack, result);
            }
            else if (prefix[i] == '/') {
                int a = stack->values[stack->top];
                int b = stack->values[--stack->top];
                result = a / b;
                Pop(stack, x);
                Push2(stack, result);
            }
            else {          //num
                if (strlen(prefix[i]) == 1) {
                    Push2(stack, int(prefix[i]) - 48);
                }
                else if (strlen(prefix[i]) > 1 ) {
                    Push2(stack, atoi(prefix[i])); // atoi 的错误返回为0,所以有些局限性而且只能返回整形可以自己实现
                }
            }
        }
        return result;
 
}

可以看看