-
2021-12-27 12:48:58
.
#include<iostream> using namespace std; class RPN { int a[999];//数字 int top = 999; public: RPN() { for (int i = 0;i <999; i++) a[i] = { 0 }; } ~RPN(){} void push(int x) { top--; a[top] = x; } int pop() {//删除栈顶数据; char x = a[top]; top++; return x; } bool empty() { if (top == 999) return 1; return 0; } int Val(char *data) {//输入进来字符串 //然后判断,是数字还是符号,数字进栈,符号出栈 while (*data != '\0') { char ch = *data; int z=0; if (ch >= '0' && ch <= '9') { push(ch-'0'); } else { int x, y; x = pop(); y = pop(); switch (ch) { case'+': z = x + y; break; case'-': z = x - y; break; case'*': z = x * y; break; case'/': z = x / y; break; case'%': z = x - y; break; default: break; } push(z); } data++; } if (empty() == false) { int i = a[998]; return i; } return 0; } }; int main() { char data[999]; cin >> data; RPN r; cout<<r.Val(data)<<endl; return 0; }
更多相关内容 -
后缀表达式计算
2022-01-12 15:01:52后缀表达式计算上期回顾
我们上期学习由中缀表达式转为后缀表达式 但是没有进行计算。这一期我们进行后缀表达式计算讲解。
由中缀表达式转化为后缀表达式我们还是得到一个以空格分隔好的字符串。我们现在考虑的是计算问题。所以其实大体思路和中缀表达式计算基本相似。下面是我对其进行分析实现。
思路分析
首先 我们由上期文章学会了把一个中缀表达式转化为后缀表达式了,可是得到的式子却和中缀表达式不完全相同(格式上)。我们得到的后缀表达式只有数字和操作符 而且都是已经拿空格把他们分隔开了。所以现在我们只需要对其遍历进行计算。
定义一个字符串 我们还是拿老例子来说。通过调用我们学过的中缀转后缀表达式的类中转化的方法函数来进行直接转化。转化方法是用static进行修饰的,所以我们直接用类名点方法名直接调用,传入我们定义好的字符串,赋给新的字符串。这样我们的后缀表达式就产生了。
代码实现:
String infixExpression = "(10+20/2*3)/2+8"; String suffixExpression = InfixToSufix.infixToSuffix(infixExpression);
我们现在得到后缀表达式了 就是进行计算。在这里我们用到一个辅助栈用来存放数字就可以 因为操作符不需要进栈 直接在外进行使用即可。所以定义的stack就是Integer类型的。我们还是要用split()方法以空格分割字符串,放入字符串数组中,以便更好地去遍历。
现在对字符串数组进行遍历。首先要把空字符串滤除掉。然后再去进行判断是否为数字(还是定义一个函数方法isNumber)还是操作符;当遍历到数字的时候,直接让数字进栈即可(注意: 我们遍历到的数字是以字符串形式的格式遍历的,而我们进栈的是数字格式,所以在这里还得把字符串改为数字格式。new Integer(token) 方法有很多种)。如果遍历到操作符我们就直接进行计算操作(在定义一个函数方法 processAnOperator()传入栈和操作符两个参数)。最终我们会得到一个最终结果在栈顶 最后把栈顶数字弹出即是我们最终后缀表达式计算的结果。
代码实现
private static int evaluateSuffix(String expression) { ArrayStack<Integer> stack = new ArrayStack<>(); String[] tokens = expression.split(" "); for (String token : tokens){ if (token.length() == 0){ continue; } if (isNumber(token)){ stack.push(new Integer((token))); }else { processAnOperator(stack,token); } } return stack.pop(); }
上述提及到两个附加函数方法是isNumber()和processAnOperator();我们现在对齐进行讲解分析。
isNumber()方法是在遍历数组的时候判断是否为数字的,我们使用到maches("\\d+");这就是对其进行数字匹配我们在上期学习中也提及到。为了巩固知识 起到让我们牢记的作用。我们大概讲一下。里面参数是用 \ 来对 \d 进行转转义的,是判断数字的方法 如果数字和其他字符参杂就会报错以及至少要有一个数字即可。我们在这直接使用maches()返回true或者false即可。
private static boolean isNumber(String token) { return token.matches("\\d+"); }
processAnOperator()方法是我们计算的方法 传入两个参数是栈stac和遍历到的操作符token;
先把数字进栈 如果遇到操作符弹出两个数字进行计算,先弹出的放在后面,第二出来的放在前面进行计算。把计算结果在此进栈,不断的去遍历直到遍历完。最终计算完栈顶应该有一个最终结果。最后弹出即可。
private static void processAnOperator(ArrayStack<Integer> stack, String token) { int num1 = stack.pop(); int num2 = stack.pop(); if (token.equals("+")){ stack.push(num2+num1); }else if (token.equals("-")){ stack.push(num2-num1); }else if (token.equals("*")){ stack.push(num2*num1); }else if (token.equals("/")){ stack.push(num2/num1); } }
所有代码思路我们都逐个进行了讲解 最终就可以得到后缀表达式的结果啦。我会不断的更新学习体会,与君共勉,请大家多关注关注。有问题可私信也可评论!谢谢各位读者的光临!
完整代码
package p2.线性结构; import static jdk.nashorn.internal.runtime.JSType.isNumber; //后缀表达式计算 //中缀表达式转为后缀表达式 最终得到 10 20 2 / 3 * + 2 / 8 + public class SuffixCalculator { public static void main(String[] args) { String infixExpression = "(10+20/2*3)/2+8"; String suffixExpression = InfixToSufix.infixToSuffix(infixExpression); int result = evaluateSuffix(suffixExpression); System.out.println(result); } private static int evaluateSuffix(String expression) { ArrayStack<Integer> stack = new ArrayStack<>(); String[] tokens = expression.split(" "); for (String token : tokens){ if (token.length() == 0){ continue; } if (isNumber(token)){ stack.push(new Integer((token))); }else { processAnOperator(stack,token); } } return stack.pop(); } private static void processAnOperator(ArrayStack<Integer> stack, String token) { int num1 = stack.pop(); int num2 = stack.pop(); if (token.equals("+")){ stack.push(num2+num1); }else if (token.equals("-")){ stack.push(num2-num1); }else if (token.equals("*")){ stack.push(num2*num1); }else if (token.equals("/")){ stack.push(num2/num1); } } private static boolean isNumber(String token) { return token.matches("\\d+"); } }
运行结果
-
C语言后缀表达式计算.doc
2021-05-20 08:08:19C语言后缀表达式计算一、设计思想计算算数表达式并求值,采取的共有两种方法:先将算数表达式转化为后缀表达式,然后对后缀表达式进行计算。对算数表达式进行直接的计算。第一种算法这种解决方案又分为两步:1.将...C语言后缀表达式计算
一、设计思想
计算算数表达式并求值,采取的共有两种方法:
先将算数表达式转化为后缀表达式,然后对后缀表达式进行计算。
对算数表达式进行直接的计算。
第一种算法
这种解决方案又分为两步:
1.将表达式先转化为后缀表达式的字符串数组
2.利用后缀表达式进行计算
在转化过程中,第一,建立一个存符号的栈,和一个字符串数组,用来存放转化以后的表达式
然后,对于得到的用户输入的字符串进行逐个的扫描,如果是数组或者小数点,则直接存放到数组中,并且在后面加入一个分隔符,如果是操作符,则和栈中的已存的进行比较,如果比栈中的操作符的优先级高,则直接入栈,如果优先级低或相等,则栈中元素出栈,存到字符串中,然后再次检查栈顶,直到栈中元素的优先级低于扫描操作符,则此操作符入栈,然后扫描下一个字符,直到遇到字符串的结束符号\0,扫描结束。数组中存的就是后缀表达式。得到后缀表达式后,进行计算,要用到数值栈。首先要将字符表示的数字转化为浮点小数,然后进行扫描,遇到数值,放入栈中,遇到操作符,就从栈中取出两个数,进行计算后再放入栈中,扫描下一个,最后的计算结果就存到了栈中,直接取出栈内元素,就是计算的最后结果。
第二种算发
首先要建立两个栈,一个用来存放操作符,一个用来存放数值。开始对用户输入的字符串进行扫描,如果是数字字符或者小数点,则将字符转化为浮点数存到数栈里,如果是操作符,则观察符号栈,如果栈顶元素的优先级低于观察的操作符,则操作符入栈,如果栈顶元素的优先级高于或者等于观察的操作符,则从数值栈中取出两个浮点数,从符号栈中取出栈顶的操作符,然后进行相应的数值计算,所得的结果再存到数值栈中,重复这样的操作,直到符号栈中栈顶元素的优先级低于观察的操作符,则此操作符入栈,然后对下一个字符进行扫描。如果是左括号,则不进行优先级的比较,直接入栈,入栈后优先级为-1。如果是右括号,则从数值栈中取两个操作数,符号栈中取出一个符号,然后进行计算后得数放入数栈中,不断进行此类操作,直到从栈中取出的是左括号为止,左括号去掉,扫描下一个。扫描结束后,计算也结束了,计算的结果就存放在数值栈中,最后把数值栈中的数取出,就是所得的计算结果。
容错的算法简要:
括号匹配:当扫描到左括号是,左括号直接入栈,扫描到右括号时,则左括号出栈,如果栈为空,则右括号多,如果最后栈中还有括号,则左括号多。给出错误提示。
除数不为0:当扫描到'/'时,就判断其后面的数字是否为0,如果为0报错。
取余运算:取余运算时,操作数判断是否为整数,不为整数报错。
二、算法流程图
第一种算法:先将表达式转化为后缀表达式,然后计算
其主函数流程图为:
图1 主函数算法流程图
其中将中缀表达式转化为后缀表达式的主要流程为:
图2 中缀转化为后缀算法流程图
后缀表达式的计算,实现的流程图为:
图3 后缀表达式计算算法流程图
下面介绍直接计算出结果的算法的实现:
图4 直接计算中缀表达式算法流程图
三、源代码
下面给出的是用先转后缀再计算和直接计算的算法实现的程序的源代码:
#include /*导入需要用到的各种包*/
#include
#include
typedef struct /*定义结构体用来存储操作符*/
{
char op; /*存储字符*/
int level; /*存储优先级*/
}OpNode;
typedef struct
{
OpNode op[100];
int top;
int size; /*表示栈内元素的个数*/
} stack; /*定义符号栈*/
void init(stack *st) /*初始化栈*/
{
st->size=0;
st->top=0;
}
OpNode pop(stack *a) / *出栈*/
{
if (a->size==0) /*如果栈为空结束操作*/
{
exit(-1);
}
a->size--;
return a->op[--(a->top)]; /*取出栈顶元素*/
}
void push(stack *a,OpNode op) /*入栈函数*/
{
a->size++;
a->op[(a->top)++]=op;
}
OpNode
-
C++后缀表达式计算
2019-11-19 22:32:17C++后缀表达式计算 继续上篇文章,实现计算器简单计算的功能 上篇文章C++中缀表达式转后缀表达式已经将中缀表达式转换成后缀表达式并保存在队列q中 后缀表达式算法思想: 读取队列q顶端元素,并判断元素类型...C++后缀表达式计算
继续上篇文章,实现计算器简单计算的功能
上篇文章C++中缀表达式转后缀表达式已经将中缀表达式转换成后缀表达式并保存在队列q中
后缀表达式算法思想:
-
读取队列q顶端元素,并判断元素类型
(1)若是数,将数压入运算栈sum中;
(2)若是运算符,取出栈sum顶端的两个元素计算,结果压回栈sum; -
将队列顶端元素出栈,重复1操作,直至队列为空,此时sum中结果即为中缀表达式运算结果。
队列顶端元素对应类型值
代码
#include <iostream> #include<string> #include <stack> #include <queue> using namespace std; stack<char> s;//存放运算符的栈 queue<string> q;//输出队列(用于计算后缀表达式) stack<double> sum;//用于计算后缀表达式 string str = "";//读取整个数字串并保存 int isp(char c)//栈内元素优先级判断 { switch (c) { case '#': return 0; case '(': return 1; case '+': case '-': return 3; case '*': case '/': case '%': return 5; case ')': return 6; } } int icp(char c)//栈外元素优先级判断 { switch (c) { case '#': return 0; case ')': return 1; case '+': case '-': return 2; case '*': case '/': case '%': return 4; case '(': return 6; } } void postfix(string input)//中缀表达式转后缀表达式代码 { s.push('#');//将#压入栈顶 input += '#';//添加#号作为结束符 for (int i = 0; i < input.length(); i++) { if ((input[i] >= '0' && input[i] <= '9') || input[i] == '.') { str += input[i]; } else { if (str.length() > 0)//将数放入直接输出到队列中 { q.push(str); str = ""; } while (isp(s.top()) > icp(input[i])) { string a;//因为不能直接在栈和队列间转换字符和字符串类型,所以先将字符转成 字符串再出栈进队列 a = s.top(); q.push(a); s.pop(); } //判断站外元素优先级决定元素是应该去除(=),还是进栈(<) if (isp(s.top()) == icp(input[i])) { s.pop(); } else { s.push(input[i]); } } } } int wordType(string str)//队列顶元素类型 { if (str == "+") { return 1; } else if (str == "-") { return 2; } else if (str == "*") { return 3; } else if (str == "/") { return 4; } else { return 0;//元素数字 } } void addOperation()//加运算,取运算栈的两个栈顶元素进行操作,结果压回运算栈 { double temp1, temp2,result; temp2 = sum.top();//先取操作数2(运算符后面的操作数) sum.pop(); temp1 = sum.top();//再取操作数1(运算符前面的操作数) sum.pop(); result = temp1 + temp2; sum.push(result); } void subOperation()//减运算 { double temp1, temp2, result; temp2 = sum.top(); sum.pop(); temp1 = sum.top(); sum.pop(); result = temp1 - temp2; sum.push(result); } void mulOperation()//乘运算 { double temp1, temp2, result; temp2 = sum.top(); sum.pop(); temp1 = sum.top(); sum.pop(); result = temp1 * temp2; sum.push(result); } void divOperation()//除运算 { double temp1, temp2, result; temp2 = sum.top(); sum.pop(); temp1 = sum.top(); sum.pop(); result = temp1 / temp2; sum.push(result); } void suffix()//计算后缀表达式,结果保留在栈sum中 { while (q.empty() == false) { int objType;//队列顶元素的类型(0:数字;1:+;2:-;3:*;4:/) objType = wordType(q.front()); switch (objType) { case 0: sum.push(atof(q.front().c_str())); break;//使用c_str()方法将string转换成double型,将数字放入计算栈中 case 1: addOperation(); break; case 2: subOperation(); break; case 3: mulOperation(); break; case 4: divOperation(); break; } q.pop(); //将队列顶元素出队列 } } int main() { string input; string och; cin >> input; postfix(input); //while (q.empty() == false)//队列不为空则输出队列元素 //{ // och = q.front(); // cout << och; // q.pop(); //} suffix(); cout << sum.top() << endl; }
实验结果
结果正确,自行验证。 -
-
C语言数据结构-栈-后缀表达式计算
2021-03-26 18:41:31栈 后缀表达式计算 请使用已定义好的栈完成后缀表达式计算: (1)如果是操作数,直接入栈 (2)如果是操作符op,连续出栈两次,得到操作数x 和 y,计算 x op y,并将结果入栈。 后缀表达式示例如下: 931-3*+102/+ ... -
后缀表达式计算器.cpp(C++)
2019-01-09 19:15:57C++的后缀表达式计算器,运用栈,可以方便地得出浮点数运算的结果。支持的运算符有+、-、*、/、&、|、^、<(左移)、>(右移)、`(乘方)、!(整数阶乘)、\(绝对值),其中整数阶乘和绝对值是单目运算符,其它的... -
前缀表达式计算、中缀表达式计算、后缀表达式计算
2020-11-03 20:43:42首先要知道什么是前缀表达式,什么是中缀表达式,什么是后缀表达式 所谓的中缀表达式就是类似于这种的运算1+((2+3)×4)-5 所谓的前缀表达式就是符号在两个操作数的前面- + 1 × + 2 3 4 5 所谓的后缀表达式就是两... -
数据结构表达式的两种计算方法x_如何求数据结构的后缀表达式
2020-06-14 08:50:42欢迎下载 欢迎下载 PAGE # 设计思想 一 先将...因此我 们需要有一种更能使计算机理解的不用考虑优先级也不包括括号的表达式 也就是后缀 表达式我们可以借助栈将其实现 首先 我们需要将中缀表达式转换为后缀表达式 这 -
C++ 使用后缀表达式计算数学表达式 支持小数、负数计算
2019-09-17 17:32:01后缀表达式,简单地说,就是一种运算符在操作数后面的表达式,后缀表达式有个很重要的特点就是可以去掉中缀表达式的括号但是又保留运算的优先级,这样便于计算机计算表达式。而我们数学上使用的是中缀表达式,... -
根据后缀表达式计算结果(Java实现)
2020-04-07 11:34:25在上一篇中缀表达式转换为后缀表达式,我们已经将中缀表达式转换为了后缀表达式,接下来我们看看怎么根据后缀表达式计算出结果。 先创建一个数据结构,栈,作为存储。 ... -
栈 后缀表达式计算(icoding)
2021-08-04 12:11:59请使用已定义好的栈完成后缀表达式计算: (1)如果是操作数,直接入栈 (2)如果是操作符op,连续出栈两次,得到操作数x 和 y,计算 x op y,并将结果入栈。 后缀表达式示例如下: 931-3*+102/+ 13445+51/6- 操作数、... -
中缀表达式转后缀表达式计算
2009-10-02 18:29:00后缀表达式计算过程的规则非常简单:从左到右依次扫描,当读到运算符时,就对该运算符前面的两个操作数执行相应的运算,直至得到表达式的结果。 编写程序模拟编译系统计算中缀表达式的过程,大体分为两步: (1) 将... -
栈应用之 后缀表达式计算 (python 版)
2020-12-08 05:50:55栈应用之 后缀表达式计算 (python 版)后缀表达式特别适合计算机处理1. 中缀表达式、前缀表达式、后缀表达式区别中缀表达式:(3 - 5) * (6 + 17 * 4) / 3 17 * 4 + 6前缀表达式:/ * - 3 5 + 6 * 17 4 3 * 17 4 + 6... -
后缀表达式计算的代码实现
2020-10-21 21:01:38import java.util.ArrayList; import java.util.List; import java.util.Stack; public class ... //先定义一个逆波兰表达式 (3+4)×5-6 ===> 3 4 + 5 × 6 - String suffixExpression = "30 4 + 5 * 6 - -
PTA 6 后缀表达式计算 (100 分)
2022-03-24 23:41:34Kunkun学长觉得应该让学弟学妹了解一下这个知识点:后缀表达式相对于中缀表达式更容易让计算机理解和学习。现在kunkun学长给出一串后缀表达式,你能帮他算出这个后缀表达式的值吗? 输入格式: 第一行输入后缀... -
c++ 实现后缀表达式计算(数据结构)
2019-09-28 20:28:11开始计算 int count(Stack * top,char oper){ int v1 = pop(top); int v2 = pop(top); int result = 0; switch(oper){ case '+':result = v2 + v1;break; case '-':result = v2 - v1;break; case '*':... -
后缀表达式计算java
2019-06-16 01:28:27//表达式输入,结果展示 public static void main(String args[]){ String source="(2+9)/3-5"; String end=new CD().start(source); System.out.println(end); } //接收表达式,进行大致的处理 public ... -
后缀表达式计算方式
2020-10-12 19:18:25例题:后缀表达式:9 3 1-3*+ 10 2/+ 规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。 具体:详解后缀表达式 ... -
简单的后缀表达式计算
2020-01-26 20:49:35简单的后缀表达式计算 (简单不是指代码简单,而是要计算的表达式简单) 什么是后缀表达式? 百度百科传送门 最简单后缀表达式: a b + 一眼可以看出结果是 a + b,就是先将前面的数字存起来,遇到运算符,取两个... -
四川大学计算机学院-数据结构与算法分析高分实验报告-利用后缀表达式计算中缀表达式的值.rar
2021-08-18 21:00:57四川大学计算机学院-数据结构与算法分析高分实验报告-利用后缀表达式计算中缀表达式的值.rar 都是自己非常认真完成的,每一个要点都实现到位,还额外实现了创新内容。 最后得到的分数也很好 -
C语言后缀表达式计算资料.pdf
2022-03-15 17:35:37C语言后缀表达式计算资料.pdf -
中缀后缀表达式计算.pdf
2021-10-20 11:13:31中缀后缀表达式计算.pdf -
前缀、中缀、后缀表达式计算和转化算法详解
2020-07-21 18:48:28前缀、中缀和后缀表达式 概述 前缀、中缀、后缀表达式是对表达式的不同记法,其区别在于运算符相对于数字的位置不同,前缀表达式...对计算机来说,计算前缀或后缀表达式的值非常简单。 中缀转换为前缀、后缀 **以 1+(2 -
咸鱼学数据结构和算法——后缀表达式计算机求值
2021-01-18 22:16:10本文主要介绍后缀表达式计算机求值算法和代码实现 -
后缀表达式c++实现代码
2018-09-30 11:46:01std::string src = argc > 1 ? argv[1] : "12+((2+73)*4)-15"; std::cout ; Expression expression; Expression::PrefixType result; int ret = expression.ToPrefix(src, result); if (ret !... } -
C++利用栈实现中缀表达式转后缀表达式
2020-12-20 20:40:51本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 题目:现有中缀表达式如:1+(2-3)*4+10/5 请用栈的特性编写一个程序,使得程序输出后缀表达式 分析如下: STEP1: 1+(2-3)...