本文将介绍中缀表达式计算器的详细写法,是C语言把中缀表达式转换为后缀表达式和C语言逆波兰计算器的结合 但本篇用了更精简的写法，但是也相对的提高了代码的理解难度，在阅读时，需自己详细斟酌
版权声明：本文为博主原创文章，转载请注明博客地址： https://blog.csdn.net/zy010101/article/details/82728726
题目： Evaluate the value of an arithmetic expression in Reverse Polish Notation.
今天来写一下栈在求值表达式里的应用，这部分看了差不多一天了，具体原理基本懂了，代码实现部分只实现了无括号情况下的中缀表达式转后缀表达式，因为没找到标准的C代码实现，所以一直自己摸索，今天就来写一写原理以及已经实现的代码。
像 * 这种操作符( operator ) 介于操作数 ( operand )中间的表示法,称为 "中缀" 表示法.
线性表是最为常用的数据结构之一，其他高级语言也都有提供，也就是Java、Python中的List
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
算数混合四则运算求值 [问题] 利用算符优先关系，实现对算术四则混合运算表达式的求值 [要求] 输入的形式：表达式，例如2*(3+4) 包含的运算符只能有’+’ 、‘-’ 、‘*’ 、‘/’ 、‘(’、 ‘)’； 输出的形式：运算结果，例如2*(3+4)=14； 程序所能达到的功能：对表达式求值并输出 思路：利用栈实现表达式求值，需要思考如下问题： 算符的优先级 字符转换成数字（包括解析小数） 主要思路： 算术表达式有三种类型：前缀，中缀，后缀表达式，而这里主
前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
如果用字符的话，单个的数字或者符号，比如其中的 ‘5’、’*’、’3’、’(‘ 等轻易就会识别出来
之前我们介绍过了什么是后缀表达式,以及它如何通过中缀表达式进行转换,以及关于后缀表达式的求值问题,如有遗忘👉🔗http://t.csdnimg.cn/Hl4Y9
这是国内第一个关于Nim的系列教程 先说废话 业内的人认为能够直接操作系统硬件的语言才称得上系统级的编程语言 常见的系统级编程语言有：汇编、C、C++、D、GO、Rust、Nim。 像python、Java、c#、VB、JavaScript、PHP等，要么需要虚拟机、要么需要解释器，都称不上系统级的编程语言，都受限于它们所依赖的环境。 系统级的编程语言就不会这样，自由度非常高， 但汇编、C、C++的生产效率都比较底下 虽然C++用熟练了之后，生产效率不一定低，但这门语言的复杂度非常高，学习曲线很陡 那么就剩
<操作数><操作符><操作数> 就像我们平时用到的大部分计算表达式都是中缀 比如 1+1 3*2 等等 中缀表达式虽然很方便人使用，但是对机器却不太友好 比如我要计算(1+1)*3+2 机器将怎样区分操作符的优先级，机器不是人，机器是很傻的，所以我们要提供一种新的算法，让机器无脑就可以算。 这时候就要引出 后缀表达式
1.什么是中缀表达式？ 中缀表达式示例 2.什么是后缀表达式？ 后缀表达式示例 3.代码 package xmht.datastructuresandalgorithms.datastructure.stack; import java.util.ArrayList; import java.util.List; import java.util.Stack; /** * @author shengjk1 * @date 2020/2/16 */ /* 仅仅适用于 int 类型计算 */ p
除了前边博客中介绍的基本运算符外，Swift中还支持更多高级运算符，也支持开发者进行运算符的自定义。Swift中的算符运算符有一个特点，其不会产生溢出，如果有操作产生溢出，程序会直接抛出异常。如果开发者在开发中需要有溢出操作，需要使用溢出操作符来实现。
刚开始学习c语言时，我们都学过输入一个数在输入一个操作数在输入要进行的计算方式，在输入另一个操作数，然后通过内置的+ - / 以及内置头文件 *math.h等操作进行计算 但是我们可不可以直接输入我们熟悉的算式才得出结果呢，答案是肯定的，我博客上一篇介绍了C语言把中缀表达式转换为后缀表达式有兴趣的读者可以去看看，有了上篇的知识，在加上本篇的内容就可以很容易做出一个中缀表达式计算器了有兴趣的读者可以看完本文去尝试一下，对自己的能力也是一种提升
因为比较懒，而刚好在网上看到画的还不错的图，所以就直接贴过来了哦。希望作者不要怪罪哦。。。 遇到a，直接输出：
a.数字直接输出 b.运算符 情况一：遇到左括号直接入栈，遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出，同时左括号出栈但是不输出。
// 后缀表达式转中缀表达式，同时求值，O(n) // 数值栈 vector<int> nums; // 运算符栈 vector<char> ops; // 优先级 int grade(char op) { switch (op) { case '(': return 1; case '+': case '-': return 2; case '*': case '/': return 3; } return 0; } // 处理后缀表达式中的一个运算符 void
上次介绍如何利用栈实现中缀表达式求值，如果我是出题官，当然要考前缀，后缀，中缀表达式相互转换，然后就变成了利用栈实现前缀和后缀表达式求值。
可以直接得出计算结果：-7。对于人类来说，我们很容易计算出来，因为我们从左往右看，看到后面括号时，知道括号内的计算优先级最高，因此可以先计算括号内的，然后反过来计算乘法，最后计算加法，得到最终结果。
中缀表达式转后缀表达式思路： 1.初始化一个运算符栈s1和存储中间结果的List集合s2； 2.从左至右扫描中缀表达式（这里为了方便把中缀表达式字符串依次存放到数组中）; 3.遇到操作数时，将其加到s2； 4.遇到运算符时，比较其与s1栈顶运算符的优先级： 4.1.若s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈 4.2.若优先级比栈顶运算符优先级高，也将运算符压入s1； 4.3.否则，将s1栈顶的运算符弹出并加到s2中，再次回到4.1与s1中新的栈顶运算符相比较 5.遇到括号时： 5.1.若是左括号“（”，则直接压入s1； 5.2.若是右括号“）”，则依次弹出s1栈顶运算符并加入s2，直到遇左括号为止，此时将这一对括号丢弃； 6.重复2-5，直到表达式最右边 7.将s1中剩余的运算符依次弹出并加入到s2 8.依次输出s2中的元素，结果即为中缀表达式对应的后缀表达式。
分析： 二进制化八进制：从低位（右）往高位（左），每三位直接换成八进制即可。 (1001101011)2 = (10 0110 1011)2 = (26B)16 二进制化十六进制：从低位（右）往高位（左），每四位直接换成十六进制即可。 (1001101011)2 = (1 001 101 011)2 = (1153)8 这里可以看出，D答案和A、C答案都不相同，答案必然就是D。
摘要:本文是看《大话数据结构》栈章节的学习总结 正文: 栈的应用——四则运算表达式 栈的应用场景有很多，如浏览器的后退，编辑软件的回退等，今天要谈的是栈的基本应用之四则运算表达式(中缀转后缀表达式) 大家都知道用计算器可以很方便的计算出两数运算的结果，但是如果遇到有优先级的四则运算，计算器又是如何去精确的计算出结果呢？ 在20世纪50年代有一个叫Jan Łukasiewicz的波兰数学家想到了一种不需要括号的后缀表达式，我们称为逆波兰表示法 ，逆波兰记法不需要括号来标识操作符的优先级 中缀转后缀表达
由节点（Node）组成的数据结构，其中每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以是单向的（只有指向下一个节点的指针）或双向的（有指向上一个节点的指针）。链表的节点可以动态地添加或删除，因此适用于需要频繁插入或删除元素的场景。
c#include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <string.h> #include <conio.h> /*字符操作函数*/ #include <ctype.h> #define BUFFSIZE 32 #define COL 128 #define ROW 64 // 来自公众号：c语言与cpp编程 #include <stdio.h> #include <malloc.h> #include <st
栈的操作我相信大家都应该了解了弄懂了， 如果没弄懂希望可以去再去看看相关的资料，我博客中的C语言中缀表达式转后缀表达式中涉及到了一下栈的基本操作，有兴趣的朋友也可以看看。 所谓共享栈，就是两个栈共同使用一块内存空间，其中一个栈的栈底作为另一个栈的栈顶，反之亦然。
问题引入：算术表达式计算是编译系统中的一个基本问题，其实现方法是堆栈的一个典型应用。任何一个算术表达式都是由操作数、运算符和分界符组成的。操作数和运算符是算术表达式的主要部分，分界符标志了一个算术表达式的结束。我们称操作数、运算符、分界符为一个算术表达式的单词。这里为了方便，只设计了加、减、乘、除运算。 算术表达式的计算分为两步：
中缀表达式，大家最熟悉了。就是运算符在操作数中间。像这样： 1 + 2 * 3 + 4 它的特点是： 运算符和操作数必须依次间隔出现，不允许两个操作数中间没有运算符，也不允许两个运算符中间没有操作数。 备注：一元运算符等特殊情况除外。 如果要改变表达式的计算顺序，只有一种方法，加括号，像这样： (1 + 2) * (3 + 4) 括号的本质： 括号其实是提高了括号里面运算符的优先级，而且括号嵌套的层次越多，它里面的运算符的优先级提高的就越多。 中缀和括号的优点： 非常直观，特别适合人类理解。 中缀和括号的缺点： 不够纯粹，毕竟括号和普通运算符是不一样的。还有就是计算机无法直接计算。 于是一个波兰的数学家就想办法把括号去掉了，就是下面这个。 前缀表达式，运算符写在前面，操作数写在后面，像这样： * + 1 2 + 3 4 这就是上面那个带括号的对应的前缀形式，可以看到括号已经没有了。 它的特点是： 以运算符开头，以操作数结尾，除此之外没有什么特点，且一眼看上去根本看不出对错，多个运算符可以挨在一起，多个操作数也可以挨在一起。特别是初学者，一定要记住这些，不要受中缀的影响。 大家为了纪念这哥们儿，也称这种形式为“波兰式”。 不得不说，人类还是很善于思考的，既然运算符在操作数前面是可以的，那么倒过来是不是也可以啊？ 后缀表达式，操作数写在前面，运算符写在后面，像这样： 1 2 + 3 4 + * 这就是上面那个带括号的对应的后缀形式，可以看到括号也已经没有了。 它的特点是： 以操作数开头，以运算符结尾，然后就和前缀是一样的，一眼看不出对错，运算符可以挨着，操作数可以挨着，这里再次提醒初学者，要记住这些特点。 由于这种形式和“波兰式”正好相反，因此也称为“逆波兰式”。 后缀式和前缀式的计算过程 表达式的计算要用到栈，所以先准备两个栈，一个用红色标记，一个用绿色标记。 后缀式的计算过程，先看动画，再看分步解析：
人们的日常习惯是把算术表达式写成中缀式，但对于机器来说更“习惯于”后缀式，关于算术表达式的中缀式和后缀式的论述一般的数据结构书都有相关内容可供参看，这里不再赘述，现在你的任务是将中缀式变为后缀式。
我们正常写的表达式，就比如题目中的这个：(2 + 1) * 3 这种写法叫做中缀算术表达式，即运算符写在操作数的中间，但是这种写法计算机是不能直接计算的，因为涉及运算符优先级的问题，比如1+2*3，应该先算*。 所以呢，这里就需要我们做一件事情，就是把它变成后缀表达式，其实就是根据优先级对表达式中的运算符排一个序，并且放到对应的操作数后面。 就比如题目中给的这个示例：((2 + 1) * 3)这个表达式对应的后缀表达式就是["2","1","+","3","*"]（题中是把它放到一个字符串数组中了）。 即1和2先进行后面的+，得到的结果再和3进行后面的*，得到最终结果。这样就直接从前往后算，不用考虑优先级的问题了。
后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。
可能有读者会疑惑我们为什么将num定义为int，我们这么做的原因是为了简便，或者说就是偷懒吧，因为如果要支持使用者输入小数，那么我们的程序在获取、处理输入方面的代码会更加复杂一点╮(╯_╰)╭。关于如何获取、处理输入，我们将在本文的最后给出答案。同时也会给出完整的计算器程序代码，或者说是给出完整的只支持整数输入的、不具备查错纠错能力的四则运算计算器
温馨提示：因微信中外链都无法点击，请通过文末的” “阅读原文” 到技术博客中完整查阅版；（本文整理自技术博客）
最近在开发 APP 的过程中遇到了一个问题，即，如何计算常用数学表达式的结果，即，给定字符串8 - (6 + 4 / 2 - 1) * 2，怎么计算得到结果。
表达式求值对于有知识经验的人类而言，可以通过认知，按运算符的优先级进行先后运算。但对计算机而言，表达式仅是一串普通的信息而已，需要通过编码的方式告诉计算机运算法则。这个过程则需要借助于栈来实现。
自认脑袋不够大，就实现一个普通版本的吧（支持正负数加减乘除等基本连续的运算，未提供括号功能）
1）子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
中缀转后缀 本文大部分资料参考慕课何钦铭老师的数据结构 相关的慕课链接:表达式求值 中缀表达式是最常用的算术表达式,运算符在运算数中间,运算需要考虑运算符优先级. 后缀表达式是计算机容易运算的表达式,运算符在运算数后面,从左到右进行运算,无需考虑优先级,运算呈线性结构. 先举个简单的转换例子 2+9/3-5 (前缀)-> 2 9 3 / + 5 – (后缀) 先进行乘除再进行加减 运算规律,运算数位置不变,改变的是运算符位置 可以推栈实现,用堆栈储存等待中的运算符. 将当前运算符与最后一个等待的运算符比较.
不过快乐并不长久，学校开始要求进行多个数的加减乘除并且还涉及到大中小括号的四则运算，家里的老式计算器不好使了。9+（3-1）*3+10/2，这么简单的式子，计算器完全没有办法计算，幸好自己存了一点私房钱，买了一个高级一点的计算器，引入了四则运算表达式和括号。
数据结构与算法中经常遇到中缀表达式转前缀表达式的题目，网上的教程大都很不直观，自己学的时候，也走了很多弯路，现在把一个简单易懂的算法教程分享出来。
在函数式编程语言中，为了表示方便，出现了一些新的语法格式。所谓前缀、中缀、后缀表达式，它们之间的区别在于运算符相对与操作数的位置不同，为了说明它们的概念，首先来看一下中缀表达式。 所谓中缀表达式，就是将函数名放到两个操作数中间的表达式，其中，左侧的操作数代表函数对象或值，右侧的操作数代表函数的参数值。例如： (3 + 4) × 5 - 6 就是中缀表达式 - × + 3 4 5 6 前缀表达式 3 4 + 5 × 6 - 后缀表达式 前缀表达式 前缀表达式又称为前缀记法、波兰式，主要用于表示运算符位于操作数
表达式求值 对于表达式的求值,一般使用中缀表达式转后缀表达式后,对后缀表达式求值,因为对于后缀或者前缀表达式计算,计算的顺序都是唯一的. 中缀表达式转后缀表达式的方法： 1.遇到操作数：直接输出（添加到后缀表达式中） 2.栈为空时，遇到运算符，直接入栈 3.遇到左括号：将其入栈 4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。 5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈 6.最终将栈中的元素依次出栈，输出。123
给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
栈的英文为(stack): 又名堆栈，它是一种运算受限的线性表。限定仅在表尾(栈顶)进行插入和删除操作的线性表
栈、队列、deques、列表是一类数据的容器，它们数据项之间的顺序由添加或删除的顺序决定。一旦一个数据项被添加，它相对于前后元素一直保持该位置不变。诸如此类的数据结构被称为线性数据结构。
队列比较常用的是广度优先遍历，在树中是层序遍历，在图中是无权图的最短路径； 栈能帮助你实现深度优先遍历等；
中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9 3 1-3*+ 10 2/+” 中缀表达式转后缀表达式的方法： 1.遇到操作数：直接输出（添加到后缀表达式中） 2.栈为空时，遇到运算符，直接入栈 3.遇到左括号：将其入栈 4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。 5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈 6.最终将栈中的元素依次出栈，输出。 实现9+(3-1)*3+10/2，栈=空 1.
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
对象存储
云直播
