1. Python技术站首页
  2. C

C语言实现逆波兰式实例

• C

C语言实现逆波兰式实例

逆波兰式是一种数学表达式表示法，也称为后缀表达式。与常见的表达式表示法不同，逆波兰式将操作数放在操作符之前，能够方便地使用栈等数据结构进行表达式的求解。在C语言中实现逆波兰式求值可以采用栈的数据结构进行实现。本文将介绍基于栈的C语言实现逆波兰式的完整攻略。

逆波兰式的基本原理

逆波兰式可以通过以下步骤进行转换：

  1. 从左到右扫描中缀表达式。
  2. 遇到操作符时，将其压入栈中。
  3. 遇到操作数时，将其输出。
  4. 遇到右括号时，将操作符弹出并输出，直到遇到左括号。
  5. 如果遇到其他操作符，判断其与栈顶操作符的优先级关系，如果栈顶操作符的优先级大于该操作符，则将栈顶操作符弹出并输出，再将该操作符压入栈中。
  6. 重复步骤2-5，直到将中缀表达式转换为后缀表达式。

C语言实现逆波兰式的基本步骤

  1. 定义一个栈结构体，包含栈顶指针以及栈的大小等信息。
  2. 定义一个函数，用于将中缀表达式转换为后缀表达式，其中使用栈来维护操作符。
  3. 定义一个函数，用于计算后缀表达式的值，其中使用栈来维护操作数。

示例说明1：将中缀表达式转换为后缀表达式

以下为一个简单的例子：

#include <stdio.h>

#define MAXSIZE 100

typedef enum {
    OP_PLUS = '+',
    OP_MINUS = '-',
    OP_MULTIPLY = '*',
    OP_DIVIDE = '/',
    OP_LEFT_PARENTHESES = '(',
    OP_RIGHT_PARENTHESES = ')',
    OP_END = '\0'
} operator;

typedef struct {
    operator* top;
    operator* stack;
    int size;
} operator_stack;

void operator_push(operator_stack* stack, operator op) {
    if (stack->top - stack->stack >= stack->size) {
        printf("stack is full\n");
        return;
    }
    *(++stack->top) = op;
}

operator operator_pop(operator_stack* stack) {
    if (stack->top == stack->stack) {
        printf("stack is empty\n");
        return OP_END;
    }
    return *(stack->top--);
}

operator operator_top(operator_stack* stack) {
    if (stack->top == stack->stack) {
        printf("stack is empty\n");
        return OP_END;
    }
    return *(stack->top);
}

operator_stack* operator_stack_create(int size) {
    operator_stack* stack = (operator_stack*) malloc(sizeof(operator_stack));
    stack->top = stack->stack - 1;
    stack->stack = (operator*) malloc(sizeof(operator) * size);
    stack->size = size;
    return stack;
}

void operator_stack_destroy(operator_stack* stack) {
    free(stack->stack);
    stack->stack = NULL;
    stack->top = NULL;
    stack->size = 0;
    free(stack);
}

int is_number(char ch) {
    return ch >= '0' && ch <= '9';
}

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

int is_higher_priority(operator op1, operator op2) {
    switch (op1) {
        case OP_DIVIDE:
        case OP_MULTIPLY:
            return op2 == OP_PLUS || op2 == OP_MINUS;
        case OP_PLUS:
        case OP_MINUS:
            return op2 == OP_LEFT_PARENTHESES;
        case OP_LEFT_PARENTHESES:
        default:
            return 0;
    }
}

void infix_to_postfix(char* infix, char* postfix, int size) {
    operator_stack* stack = operator_stack_create(size);
    operator_push(stack, OP_LEFT_PARENTHESES);
    int i = 0;
    int j = 0;
    while (infix[i] != '\0') {
        char ch = infix[i++];
        if (is_number(ch)) {
            postfix[j++] = ch;
        } else if (is_operator(ch)) {
            if (ch == OP_LEFT_PARENTHESES) {
                operator_push(stack, ch);
            } else if (ch == OP_RIGHT_PARENTHESES) {
                operator top = operator_pop(stack);
                while (top != OP_LEFT_PARENTHESES) {
                    postfix[j++] = top;
                    top = operator_pop(stack);
                }
            } else {
                operator top = operator_top(stack);
                while (is_higher_priority(top, ch)) {
                    postfix[j++] = operator_pop(stack);
                    top = operator_top(stack);
                }
                operator_push(stack, ch);
            }
        } else {
            printf("invalid character: %c\n", ch);
        }
    }
    while (stack->top != stack->stack) {
        postfix[j++] = operator_pop(stack);
    }
    postfix[j] = '\0';
    operator_stack_destroy(stack);
}

int main() {
    char infix[MAXSIZE] = "3+4*5/(6+7)-8";
    char postfix[MAXSIZE];
    infix_to_postfix(infix, postfix, MAXSIZE);
    printf("infix: %s\npostfix: %s\n", infix, postfix);
    return 0;
}

在上面的示例代码中，我们定义了一个操作符栈来维护中缀表达式转换为后缀表达式的过程。其中operator_push、operator_pop和operator_top函数是操作栈的基本函数。is_higher_priority函数用来判断两个操作符的优先级。infix_to_postfix函数用来将中缀表达式转换为后缀表达式。在实际处理过程中，我们通过扫描中缀表达式中每一个字符，然后进行相应的操作。

示例说明2：计算后缀表达式的值

以下为一个简单的例子：

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

#define MAXSIZE 100

typedef enum {
    OP_PLUS = '+',
    OP_MINUS = '-',
    OP_MULTIPLY = '*',
    OP_DIVIDE = '/',
    OP_LEFT_PARENTHESES = '(',
    OP_RIGHT_PARENTHESES = ')',
    OP_END = '\0'
} operator;

typedef struct {
    int* top;
    int* stack;
    int size;
} integer_stack;

void integer_push(integer_stack* stack, int value) {
    if (stack->top - stack->stack >= stack->size) {
        printf("stack is full\n");
        return;
    }
    *(++stack->top) = value;
}

int integer_pop(integer_stack* stack) {
    if (stack->top == stack->stack) {
        printf("stack is empty\n");
        return 0;
    }
    return *(stack->top--);
}

int integer_top(integer_stack* stack) {
    if (stack->top == stack->stack) {
        printf("stack is empty\n");
        return 0;
    }
    return *(stack->top);
}

integer_stack* integer_stack_create(int size) {
    integer_stack* stack = (integer_stack*) malloc(sizeof(integer_stack));
    stack->top = stack->stack - 1;
    stack->stack = (int*) malloc(sizeof(int) * size);
    stack->size = size;
    return stack;
}

void integer_stack_destroy(integer_stack* stack) {
    free(stack->stack);
    stack->stack = NULL;
    stack->top = NULL;
    stack->size = 0;
    free(stack);
}

int is_number(char ch) {
    return ch >= '0' && ch <= '9';
}

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

int apply_operator(int left, int right, operator op) {
    switch (op) {
        case OP_PLUS:
            return left + right;
        case OP_MINUS:
            return left - right;
        case OP_MULTIPLY:
            return left * right;
        case OP_DIVIDE:
            return left / right;
        default:
            printf("invalid operator\n");
            return 0;
    }
}

int evaluate_postfix(char* postfix) {
    integer_stack* stack = integer_stack_create(strlen(postfix) + 1);
    int i = 0;
    while (postfix[i] != '\0') {
        char ch = postfix[i++];
        if (is_number(ch)) {
            integer_push(stack, ch - '0');
        } else if (is_operator(ch)) {
            int right = integer_pop(stack);
            int left = integer_pop(stack);
            integer_push(stack, apply_operator(left, right, ch));
        } else {
            printf("invalid character: %c\n", ch);
        }
    }
    int result = integer_pop(stack);
    integer_stack_destroy(stack);
    return result;
}

int main() {
    char postfix[MAXSIZE] = "345*67+/8-";
    int result = evaluate_postfix(postfix);
    printf("postfix: %s\nresult: %d\n", postfix, result);
    return 0;
}

在上面的示例代码中，我们定义了一个整数栈来维护后缀表达式求值的过程。其中integer_push、integer_pop和integer_top函数是操作栈的基本函数。apply_operator函数用来计算两个操作数的运算结果。evaluate_postfix函数用来计算后缀表达式的值。在实际处理过程中，我们通过扫描后缀表达式中每一个字符，然后进行相应的操作。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言实现逆波兰式实例 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年5月23日
下一篇 2023年5月23日

相关文章

  • Win10运行程序提示“损坏的映像 错误0xc0000020”解决方法图文教程

    下面是详细的攻略： 问题描述 在Win10系统中运行某个程序时，系统提示“损坏的映像 错误0xc0000020”的错误消息，导致无法正常运行程序。 解决方法 方案一：重新安装程序 出现损坏映像的错误消息，可能是程序自身出现问题导致的。因此，重新安装这个程序是最直接且有效的解决方法。 具体操作步骤如下： 找到出现错误消息的程序，卸载它。 重新下载并安装程序。 …

    C 2023年5月24日
    00

  • 如何解决Win10更新错误0x8024401c怎么办？Win10更新失败错误0x8024401c的解决方法

    针对Win10更新错误0x8024401c，以下是解决方法的完整攻略： 1. 检查网络连接 首先要检查网络连接是否正常，这是Win10更新失败的主要原因之一。可以尝试以下方法进行检查： 第一步：打开浏览器，打开任意网页，查看是否能正常访问； 第二步：确保网络连接正常，并尝试重新连接； 第三步：如果网络连接正常，尝试断开并重新连接网络，查看问题是否得到解决。 …

    C 2023年5月23日
    00

  • C语言实现3个数从小到大排序/输出的方法示例

    C语言实现3个数从小到大排序/输出的方法示例 问题描述 C语言中如何实现3个数从小到大排序/输出？ 解决方案 #include <stdio.h> int main() { int a, b, c; printf("请输入三个整数：\n"); scanf("%d%d%d", &a, &b, …

    C 2023年5月30日
    00

  • C语言基于EasyX实现贪吃蛇

    C语言基于EasyX实现贪吃蛇攻略 1. 前置要求 需要具备一定的 C 语言编程和 EasyX 开发的基本知识，以及掌握贪吃蛇的游戏规则和基本操作。 2. 环境搭建 需要安装Visual Studio 2010及以上版本、EasyX图形库和EasyX官方Visual Studio插件。其中EasyX图形库可以从官方网站下载：https://www.easyx…

    C 2023年5月23日
    00

  • javascript中的括号()用法小结

    让我为你详细讲解“JavaScript中的括号()用法小结”。 标题 1. 函数调用 在JavaScript中，括号()主要用于函数调用。 函数调用是指通过函数名后加上一对括号()来执行该函数。例如： function hello() { console.log("Hello, world!"); } hello(); // 调用函数he…

    C 2023年5月22日
    00

  • 详解C++异常处理(try catch throw)完全攻略

    作为本站的作者，我非常乐意为你介绍“详解C++异常处理（try-catch-throw）完全攻略”的内容。本篇攻略将涵盖以下主题，包括异常的概念，异常处理基本原则，以及如何使用try-catch块和throw语句等。 异常的概念 在C++程序中，如果发生了意外的错误，比如说磁盘空间不足，用户输入错误的数据等，这些都不是我们程序的预期结果。这时，程序会抛出一个…

    C 2023年5月22日
    00

  • C语言解数独程序的源码

    让我们来详细讲解一下“C语言解数独程序的源码”的完整攻略。 什么是数独？ 在介绍程序之前，我们先来了解一下数独。 数独是一种智力游戏，由9×9的方格组成，分成9个3×3的小方格，在已知数的基础上填上未知的数字，使得每一行、每一列和每一个小方格内的数字均为1~9，且不重复。数独不但能训练大脑的逻辑、思维能力，还能减轻压力、增加乐趣。 源码分析 下面，我们来分析…

    C 2023年5月23日
    00

  • C#中实现Json序列化与反序列化的几种方式

    下面是关于C#中实现Json序列化与反序列化的几种方式的完整攻略。 一、前言 在C#中，常用来处理Json数据的方式是Json序列化和反序列化。在开发Web应用、移动应用等过程中，处理Json数据是很常见的操作。本文将介绍C#中实现Json序列化与反序列化的几种方式，供大家参考使用。 二、Json序列化 1.使用JavaScriptSerializer类进行…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部