论坛 › 数据结构与算法 › 利用c语言实现中缀表达式求值

小彤酱 发表于 2023-10-15 18:01:59

利用c语言实现中缀表达式求值

利用c语言实现中缀表达式求值

陶远航 发表于 2023-10-15 18:03:02

实现中缀表达式求值的一种常见方法是使用两个栈，一个用于存储操作数，另一个用于存储运算符。以下是一个简单的C语言实现：

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

#define SIZE 100

int stack;
int top = -1;

void push(int item) {
    if(top >= SIZE-1) {
      printf(\"\
Stack Overflow.\");
    } else {
      stack[++top] = item;
    }
}

int pop() {
    int item;
    if(top <0) {
      printf(\"stack under flow: invalid infix expression\");
      exit(1);
    } else {
      item = stack;
      return(item);
    }
}

int is_operator(char symbol) {
    if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol =='-') {
      return 1;
    } else {
      return 0;
    }
}

int precedence(char symbol) {
    if(symbol == '^') {
      return(3);
    } else if(symbol == '*' || symbol == '/') {
      return(2);
    } else if(symbol == '+' || symbol == '-') {
      return(1);
    } else {
      return(0);
    }
}

void InfixToPostfix(char infix_exp[], char postfix_exp[]) {
    int i, j;
    char item;
    char x;

    push('(');
    strcat(infix_exp,\")\");

    i=0;
    j=0;
    item=infix_exp[ i];

    while(item != '\\0') {
      if(item == '(') {
            push(item);
      } else if( isdigit(item) || isalpha(item)) {
            postfix_exp = item;
            j++;
      } else if(is_operator(item) == 1) {
            x=pop();
            while(is_operator(x) == 1 && precedence(x)>= precedence(item)) {
                postfix_exp = x;
                j++;
                x = pop();
            }
            push(x);
            push(item);
      } else if(item == ')') {
            x = pop();
            while(x != '(') {
                postfix_exp = x;
                j++;
                x = pop();
            }
      } else {
            printf(\"\
Invalid infix Expression.\
\");
            exit(1);
      }
      i++;
      item = infix_exp[ i];
    }
    postfix_exp = '\\0';
}

int main() {
    char infix, postfix;
    printf(\"\
Enter Infix expression : \");
    gets(infix);

    InfixToPostfix(infix,postfix);
    printf(\"Postfix Expression: \");
    puts(postfix);

    return 0;
}


这个程序首先将中缀表达式转换为后缀表达式，然后计算后缀表达式的值。注意，这个程序只处理了基本的四则运算和括号，没有处理函数、指数等更复杂的运算。如果需要处理这些运算，你需要扩展这个程序。

这个程序也没有处理错误输入的情况，如果输入的表达式不合法，程序可能会出错。在实际使用中，你需要添加错误处理代码，确保程序的稳定性。
请注意，本回答来自GPT-4
如果问题已经解决，请设置最佳答案

isdkz 发表于 2023-10-15 18:03:54

中缀表达式求值的过程可以通过将中缀表达式转换为后缀表达式再进行求值来实现。具体步骤如下：

1. 创建一个栈用于存储运算符
2. 从左到右扫描中缀表达式的每个元素
3. 如果当前元素是数字，则直接输出
4. 如果当前元素是运算符，则判断该运算符与栈顶运算符的优先级关系，如果当前运算符优先级较低，则将栈顶运算符弹出并输出，直到当前运算符优先级大于等于栈顶运算符的优先级，然后将当前运算符入栈
5. 如果当前元素是左括号，则将其入栈
6. 如果当前元素是右括号，则将栈顶元素弹出并输出，直到遇到左括号为止，左括号不输出
7. 重复2-6步，直到扫描完整个中缀表达式
8. 将栈中剩余的运算符全部弹出并输出

通过上述步骤，我们可以将中缀表达式转换为后缀表达式。接下来，我们可以通过栈来求解后缀表达式的值。具体步骤如下：

1. 创建一个栈用于存储数字
2. 从左到右扫描后缀表达式的每个元素
3. 如果当前元素是数字，则将其入栈
4. 如果当前元素是运算符，则将栈顶的两个数字弹出，并将运算结果入栈
5. 重复2-4步，直到扫描完整个后缀表达式
6. 栈中剩余的数字即为表达式的值

下面是一个完整的c语言实现：

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

#define MAX_SIZE 100

typedef struct Stack {
    int top;
    int data;
} Stack;

void init(Stack *s) {
    s->top = -1;
}

int is_empty(Stack *s) {
    return s->top == -1;
}

int is_full(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int x) {
    if (is_full(s)) {
      printf("Stack is full.\n");
      exit(1);
    }
    s->data[++s->top] = x;
}

int pop(Stack *s) {
    if (is_empty(s)) {
      printf("Stack is empty.\n");
      exit(1);
    }
    return s->data;
}

int peek(Stack *s) {
    if (is_empty(s)) {
      printf("Stack is empty.\n");
      exit(1);
    }
    return s->data;
}

int is_operator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int priority(char c) {
    if (c == '+' || c == '-') {
      return 1;
    } else if (c == '*' || c == '/') {
      return 2;
    } else {
      return 0;
    }
}

void infix_to_postfix(char *infix, char *postfix) {
    Stack s;
    init(&s);
    int i, j;
    for (i = 0, j = 0; infix[ i] != '\0'; i++) {
      if (isdigit(infix[ i])) {
            postfix = infix[ i];
      } else if (is_operator(infix[ i])) {
            while (!is_empty(&s) && is_operator(peek(&s)) && priority(infix[ i]) <= priority(peek(&s))) {
                postfix = pop(&s);
            }
            push(&s, infix[ i]);
      } else if (infix[ i] == '(') {
            push(&s, infix[ i]);
      } else if (infix[ i] == ')') {
            while (!is_empty(&s) && peek(&s) != '(') {
                postfix = pop(&s);
            }
            pop(&s);
      }
    }
    while (!is_empty(&s)) {
      postfix = pop(&s);
    }
    postfix = '\0';
}

int evaluate_postfix(char *postfix) {
    Stack s;
    init(&s);
    int i;
    for (i = 0; postfix[ i] != '\0'; i++) {
      if (isdigit(postfix[ i])) {
            push(&s, postfix[ i] - '0');
      } else if (is_operator(postfix[ i])) {
            int b = pop(&s);
            int a = pop(&s);
            int c;
            switch (postfix[ i]) {
                case '+':
                  c = a + b;
                  break;
                case '-':
                  c = a - b;
                  break;
                case '*':
                  c = a * b;
                  break;
                case '/':
                  c = a / b;
                  break;
            }
            push(&s, c);
      }
    }
    return pop(&s);
}

int main() {
    char infix, postfix;
    printf("请输入中缀表达式：");
    scanf("%s", infix);
    infix_to_postfix(infix, postfix);
    printf("后缀表达式为：%s\n", postfix);
    printf("表达式的值为：%d\n", evaluate_postfix(postfix));
    return 0;
}

Mike_python小 发表于 2023-10-15 18:05:28

问题描述：
我需要使用C语言实现中缀表达式的求值算法。请提供完整的回答，包括代码和解释。

解决方案：
要实现中缀表达式的求值，通常使用栈这种数据结构来辅助计算。以下是一个基本的中缀表达式求值算法的实现示例：


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>

// 定义栈结构
typedef struct {
    int capacity;
    int top;
    int* array;
} Stack;

// 创建一个新的栈
Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

// 判断栈是否为空
bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
bool isFull(Stack* stack) {
    return stack->top == stack->capacity - 1;
}

// 入栈
void push(Stack* stack, int item) {
    if (isFull(stack)) {
      printf("栈已满\n");
      return;
    }
    stack->array[++stack->top] = item;
}

// 出栈
int pop(Stack* stack) {
    if (isEmpty(stack)) {
      printf("栈为空\n");
      return '\0';
    }
    return stack->array;
}

// 获取栈顶元素
int peek(Stack* stack) {
    if (isEmpty(stack)) {
      printf("栈为空\n");
      return '\0';
    }
    return stack->array;
}

// 操作符的优先级
int precedence(char op) {
    switch (op) {
      case '+':
      case '-':
            return 1;
      case '*':
      case '/':
            return 2;
      case '^':
            return 3;
    }
    return -1;
}

// 执行算术运算
int performOperation(int operand1, int operand2, char operator) {
    switch (operator) {
      case '+':
            return operand1 + operand2;
      case '-':
            return operand1 - operand2;
      case '*':
            return operand1 * operand2;
      case '/':
            return operand1 / operand2;
      case '^':
            return pow(operand1, operand2); // 需要包含 math.h 头文件
    }
    return 0;
}

// 中缀表达式求值
int evaluateInfixExpression(char* expression) {
    Stack* operandStack = createStack(strlen(expression));
    Stack* operatorStack = createStack(strlen(expression));

    for (int i = 0; i < strlen(expression); i++) {
      if (expression == ' ' || expression == '\t') {
            continue;
      }
      else if (isdigit(expression)) {
            int operand = 0;
            while (i < strlen(expression) && isdigit(expression)) {
                operand = (operand * 10) + (expression - '0');
                i++;
            }
            i--;
            push(operandStack, operand);
      }
      else if (expression == '(') {
            push(operatorStack, expression);
      }
      else if (expression == ')') {
            while (!isEmpty(operatorStack) && peek(operatorStack) != '(') {
                int operand2 = pop(operandStack);
                int operand1 = pop(operandStack);
                char op = pop(operatorStack);
                int result = performOperation(operand1, operand2, op);
                push(operandStack, result);
            }
            if (!isEmpty(operatorStack) && peek(operatorStack) != '(') {
                printf("非法表达式\n");
                return -1;
            }
            else {
                pop(operatorStack);
            }
      }
      else if (expression == '+' || expression == '-' ||
               expression == '*' || expression == '/' || expression == '^') {
            while (!isEmpty(operatorStack) && precedence(expression) <= precedence(peek(operatorStack))) {
                int operand2 = pop(operandStack);
                int operand1 = pop(operandStack);
                char op = pop(operatorStack);
                int result = performOperation(operand1, operand2, op);
                push(operandStack, result);
            }
            push(operatorStack, expression);
      }
    }

    while (!isEmpty(operatorStack)) {
      int operand2 = pop(operandStack);
      int operand1 = pop(operandStack);
      char op = pop(operatorStack);
      int result = performOperation(operand1, operand2, op);
      push(operandStack, result);
    }

    int finalResult = pop(operandStack);
    free(operandStack);
    free(operatorStack);

    return finalResult;
}

int main() {
    char expression;
    printf("请输入中缀表达式：");
    gets(expression);

    int result = evaluateInfixExpression(expression);
    printf("结果为：%d\n", result);

    return 0;
}


上述示例代码中，我们使用两个栈 operandStack 和 operatorStack 来辅助求值。operandStack 用于存储操作数，而 operatorStack 用于存储运算符。

算法的基本思路是遍历中缀表达式中的每个字符，根据不同的情况进行处理。当遇到数字时，将其解析为操作数并入栈 operandStack；当遇到左括号时，将其入栈 operatorStack；当遇到右括号时，执行栈操作直到遇到左括号，并将结果入栈 operandStack；当遇到运算符时，与 operatorStack 栈顶元素比较优先级，如果优先级较低，则执行栈操作直到满足要求，并将结果入栈 operandStack。

最终，当遍历完整个表达式后，执行栈操作以处理剩余的运算符。最后，从 operandStack 中取出最终的结果即为中缀表达式的求值结果。

请注意，上述示例代码仅提供了一个基本的实现方法，并不能处理包含变量、函数调用、括号嵌套等复杂的表达式。如果需要更全面和强大的表达式求值功能，可能需要借助更复杂的编译原理相关技术。

希望以上信息能够帮助你理解中缀表达式求值的实现过程。如果有进一步的疑问，请随时追问。

球一个最佳答案谢谢啦！这对我非常重要！{:10_254:}{:10_254:}{:10_254:}

小彤酱 发表于 2023-10-15 18:34:44

Mike_python小 发表于 2023-10-15 18:05
问题描述：
我需要使用C语言实现中缀表达式的求值算法。请提供完整的回答，包括代码和解释。


int performOperation(int operand1, int operand2,char operator)这一块显示 expected initializer before 'operator'

查看完整版本: 利用c语言实现中缀表达式求值