精华内容
下载资源
问答
  • 逆波兰式计算

    2019-03-01 16:18:20
    博文链接:https://cary.iteye.com/blog/53515
  • 完整的逆波兰式计算

    千次阅读 2018-10-18 19:49:36
    这是对之前的逆波兰式计算的修改,更改思路,使得可以处理多层函数和表达式嵌套的情况,如ln(ln(3)) 这里是采用将数学函数和乘方号同样看成是一种优先级较高的操作符,进栈情况满足一般的逆波兰式,需要注意的就是...
    这是对之前的逆波兰式计算的修改,更改思路,使得可以处理多层函数和表达式嵌套的情况,如ln(ln(3))
    这里是采用将数学函数和乘方号同样看成是一种优先级较高的操作符,进栈情况满足一般的逆波兰式,需要注意的就是小数点和乘方号的区分。
    同样,这里采用数字栈和符号栈来同时表示一个表达式的逆波兰式,在数字栈中的符号位置使用MARK来标识,遇到MARK时,就去符号栈找对应的符号来计算即可。
    中体思路还是和之前差不多的。
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    #include<cctype>
    #define MAX 100
    #define MARK 65535
    
    typedef struct {
    	char data[MAX];
    	int top; 
    }SqStack;
    
    typedef struct {
    	int prior[MAX];
    	char opera[MAX];
    	int top;
    }Mark;
    
    typedef struct{
    	double data[MAX];
    	char opera[MAX];
    	int top;
    	int otop;
    }RPN;
    
    SqStack *initStack(void);
    void creatStack(SqStack *S);
    void destroyStack(SqStack *S);
    void printStack(SqStack *S);
    void rpnStack(SqStack *S,RPN *rpn,Mark *mark);
    void dealMark(RPN *rpn,Mark *mark,char ch,int pri);
    void conduct(RPN *rpn);
    
    void conduct(RPN *rpn)
    {
    	int i = 0;
    	int j = 0;
    	double temp[MAX];
    	int p = 0;
    	for(int i = 0;i<=rpn->top;i++)
    	{
    		if(rpn->data[i] == MARK)
    		{
    			switch (rpn->opera[p]){
    				case '+' :{
    					double a = temp[--j];
    					double b = temp[--j];
    					temp[j++] = a+b;
    					break;
    				}
    				case '-':{
    					double a = temp[--j];
    					double b = temp[--j];
    					temp[j++] = b-a;
    					break;
    				}
    				case '*':{
    					double a = temp[--j];
    					double b = temp[--j];
    					temp[j++] = a*b;
    					break;
    				}
    				case '/':{
    					double a = temp[--j];
    					double b = temp[--j];
    					temp[j++] = b/a;
    					break;
    				}
    				case 'c':{
    					double a = temp[--j];
    					temp[j++] = cos(a);
    					break;
    				}
    				case 's':{
    					double a = temp[--j];
    					temp[j++] = sin(a);
    					break;
    				}
    				case 'o':{
    					double a= temp[--j];
    					temp[j++] = log10(a);
    					break;
    				}
    				case 'n':{
    					double a = temp[--j];
    					temp[j++] = log(a);
    					break;
    				}
    				case '^':{
    					double a = temp[--j];
    					double b = temp[--j];
    					temp[j++] = pow(b,a);
    					break;
    				}
    			}
    			p++;
    		}
    		else
    			temp[j++] = rpn->data[i];
    	}
    	printf("result = %.2f\n",temp[0]);
    	//return temp[0];
    }
    
    void dealMark(RPN *rpn,Mark *mark,char ch,int pri)
    {
    	if(ch != '(' && ch != ')' && ch != ' ')
    	{
    		while(pri <= mark->prior[mark->top] && mark->opera[mark->top] != '(' && mark->top!=-1)
    		{
    			rpn->data[++rpn->top] = MARK;
    			rpn->opera[++rpn->otop] = mark->opera[mark->top];
    			mark->top--;
    		}
    		
    		mark->opera[++mark->top] = ch;
    		mark->prior[mark->top] = pri;
    	}
    	else if(ch == '(')
    		mark->opera[++mark->top] = ch;
    	else if(ch == ')')
    	{
    		while(mark->opera[mark->top]!='(')
    		{
    			rpn->data[++rpn->top] = MARK;
    			rpn->opera[++rpn->otop] = mark->opera[mark->top];
    			mark->top--;
    		}
    		mark->top--;
    	}	
    }
    
    void rpnStack(SqStack *S,RPN *rpn,Mark *mark)
    {	
    	int t = 0;
    	while(t<=S->top)
    	{
    		if(isdigit(S->data[t]))
    		{
    			char a[MAX];
    			memset(a,0,sizeof(a));
    			int ap = -1;
    			
    			int i = t;
    			for(;isdigit(S->data[i]);i++);
    			
    			if(S->data[i] == '.')
    			{
    				i++;
    				while(isdigit(S->data[i]))
    				i++;
    				for(int j = t;j<i;j++)
    				a[++ap] = S->data[j];
    				
    				rpn->data[++rpn->top] = atof(a);
    				t = i-1;
    			}
    			else
    			{
    				for(int j = t;j<i;j++)
    				a[++ap] = S->data[j];
    				
    				rpn->data[++rpn->top] = atof(a);
    				t = i-1;
    			}
    		}
    		else if(S->data[t] == '+' || S->data[t] == '-')
    			dealMark(rpn,mark,S->data[t],1);
    		else if(S->data[t] == '*' || S->data[t] == '/')
    			dealMark(rpn,mark,S->data[t],2);
    		else if(S->data[t] == 'c' || S->data[t] == 's')
    		{
    			dealMark(rpn,mark,S->data[t],3);
    			t = t+2;
    		}
    		else if(S->data[t] == 'l')
    		{
    			if(S->data[t+1] == 'o')
    			{
    				dealMark(rpn,mark,S->data[t+1],3);
    				t = t+2;
    			}
    			else
    			{
    				dealMark(rpn,mark,S->data[t+1],3);
    				t = t+1;
    			}
    		}
    		else if(S->data[t] == '^')
    			dealMark(rpn,mark,S->data[t],4);
    		else if(S->data[t] == '(')
    			dealMark(rpn,mark,S->data[t],5);
    		else if(S->data[t] == ')')
    			dealMark(rpn,mark,S->data[t],5);
    		else
    		continue ;
    		
    		t++;
    	}
    		
    	while(mark->top>=0)
    	{
    		
    		rpn->opera[++rpn->otop] = mark->opera[mark->top--];
    		rpn->data[++rpn->top] = MARK;
    	}
    		
    	conduct(rpn);
    }
    
    void creatStack(SqStack *S)
    {
    	char ch;
    	while(scanf("%c",&ch)==1&&ch!='=')
    	S->data[++S->top] = ch;	
    }
    
    void printStack(SqStack *S)
    {
    	int t = 0;
    	while(t<=S->top)
    	printf("%c",S->data[t++]);
    	printf("\n");
    }
    
    void destroyStack(SqStack *S)
    {
    	free(S->data);
    	free(S);
    }
    
    SqStack *initStack(void)
    {
    	SqStack *S = (SqStack *)malloc(sizeof(SqStack));
    	if(!S)
    	exit(0);
    	
    	S->top = -1;
    	
    	return S;
    }
    
    
    int main(void)
    {
    	freopen("逆波兰式.txt","r",stdin);
    	
    	SqStack *S = initStack();
    	creatStack(S);
    	printStack(S);
    	
    	Mark *mark = (Mark *)malloc(sizeof(Mark));
    	for(int i = 0;i<MAX;i++)
    	mark->prior[i] = -2;
    	mark->top = -1;
    	
    	RPN *rpn = (RPN *)malloc(sizeof(RPN));
    	rpn->otop = rpn->top = -1;
    	
    	rpnStack(S,rpn,mark);
    	
    	destroyStack(S);
    	free(rpn->data);
    	free(rpn->opera);
    	free(rpn);
    	free(mark->opera);
    	free(mark->prior);
    	free(mark);
    	
    	return 0;
    }
    
    
    
    //测试数据
    //9.4+(3.27-1.05)*3.44+10/2.1+cos(0.52)+ln(ln(3))/log(5)+3^2=
    

     

    展开全文
  • 3.计算逆波兰式 测试结果: 刷题检测网站 课前预习: 1.逆波兰式的定义,如何将中缀表达式转化成逆波兰式 2.为什么要转化成逆波兰式逆波兰式有什么优点 3.各运算符之间的优先级(+、-、*、/) 4.此计算器...

    目录

    课前预习:

     代码实现过程:

    1.先定义一下各运算符的优先级

    2.转化成逆波兰式

    3.计算逆波兰式

    测试结果:

    刷题检测网站

     

    课前预习:

    1.逆波兰式的定义,如何将中缀表达式转化成逆波兰式

    2.为什么要转化成逆波兰式,逆波兰式有什么优点

    3.各运算符之间的优先级(+、-、*、/)

    4.此计算器只支持输入非负整数数,不支持输入负数,要是非要输入负数可以这样(0-1)

     代码实现过程:

    1.先定义一下各运算符的优先级

    解释:左括号优先级最低,+-略高,*/较高,右括号最高

     
    int priority(string op)
    {
    	if (op == "(") return 0;
    	if (op == "+" || op == "-") return 1;
    	else if (op == "*" || op == "/") return 2;
    }

    2.转化成逆波兰式

    几个关键的点

    (1)碰到左括号直接进入符号栈

    (2)右括号优先级最高,遇到右括号将符号栈中的运算符添加到逆波兰式数组中,直到遇到左括号,并将左括号弹出

    (3)当前为运算符,如果栈顶的运算符优先级高于当前或等于(有些文章中将在符号栈中的运算符优先级看做高于栈外同类运算符,我这里不这样了,感觉还是我这样简单点)当前运算符,弹出栈顶运算符添加到逆波兰式数组中(循环)

    (4)最后如果符号栈非空,将符号栈中的元素弹出添加到逆波兰式数组中

    
    /*将表达式转换成逆波兰式*/
    vector<string> toPolish(string str)
    {
    	stack<string> opstack;
    	vector<string> polish;
    	string str1;
    	for (int i = 0; i < str.size(); i++)
    	{
    		if (str[i] == '(') /*左括号*/
    		{
    			opstack.push("(");
    			continue;
    		}
    		if (str[i] >= '0'&&str[i] <= '9')/*数字*/
    		{
    			str1 = "";
    			while (i < str.size() && str[i] >= '0'&&str[i] <= '9')
    			{
    				str1 += str[i];
    				i++;
    			}
    			i--;
    			polish.push_back(str1);
    			continue;
    		}
    		 
    		if (str[i] == ')')/*右括号*/
    		{
    			/*出栈,直到匹配到左括号*/
    			while (!opstack.empty())
    			{
    				if(opstack.top() != "(")
    				{
    					polish.push_back(opstack.top());
    					opstack.pop();
    				}
    				else
    				{
    					opstack.pop();
    					break;
    				}	
    			}
    			 
    		}
    		else/*加减乘除运算符*/
    		{
    			str1 = str[i];
    			while (!opstack.empty() && priority(opstack.top()) >= priority(str1))
    			{
    					polish.push_back(opstack.top());
    					opstack.pop();
    			}
    			opstack.push(str1); // 添加到符号栈中
    		}
    	}
    	//剩余的运算符添加到polish中
    	while (!opstack.empty())
    	{
    		polish.push_back(opstack.top());
    		opstack.pop();
    	}
    	return polish;
    }

    3.计算逆波兰式

    逆波兰式有个大大的优点,就是符号没有优先级,也就是说我们碰到运算符就进行运算,非常简便

    /*将逆波兰式进行计算*/
    int calculation(vector<string> polish)
    {
    	stack<int> data;
    	int a, b, c;
    	for (int i = 0; i < polish.size(); i++)
    	{
    		if (polish[i] == "+" || polish[i] == "-" || polish[i] == "*" || polish[i] == "/")
    		{
    			b = data.top(); data.pop();
    			a = data.top(); data.pop();
    			if (polish[i] == "+") c = a + b;
    			else if (polish[i] == "-") c = a - b;
    			else if (polish[i] == "*") c = a * b;
    			else if (polish[i] == "/") c = a / b;
    			data.push(c);
    		}
    		else
    		{
    			data.push(stoi(polish[i]));/*stoi函数功能:string to int */
    		}
    	}
    	return data.top();
    }

    以上就是实现过程,下面就是全部代码:

     
     #include <iostream>
    #include<stack>
    #include<vector>
    #include<algorithm>
    #include<string>
    using namespace std;
    int priority(string op);
    vector<string> toPolish(string str);
    int calculation(vector<string> polish);
    int main()
    {
    	string str = "1*(1+2*(1*2*2-3+5*1))";
    	int a = calculation(toPolish(str));
    	cout << a;
    }
    
    /*返回运算符的优先级*/
    int priority(string op)
    {
    	if (op == "(") return 0;
    	if (op == "+" || op == "-") return 1;
    	else if (op == "*" || op == "/") return 2;
    }
    
    /*将表达式转换成逆波兰式*/
    vector<string> toPolish(string str)
    {
    	stack<string> opstack;
    	vector<string> polish;
    	string str1;
    	for (int i = 0; i < str.size(); i++)
    	{
    		if (str[i] == '(') /*左括号*/
    		{
    			opstack.push("(");
    			continue;
    		}
    		if (str[i] >= '0'&&str[i] <= '9')/*数字*/
    		{
    			str1 = "";
    			while (i < str.size() && str[i] >= '0'&&str[i] <= '9')
    			{
    				str1 += str[i];
    				i++;
    			}
    			i--;
    			polish.push_back(str1);
    			continue;
    		}
    		 
    		if (str[i] == ')')/*右括号*/
    		{
    			/*出栈,直到匹配到左括号*/
    			while (!opstack.empty())
    			{
    				if(opstack.top() != "(")
    				{
    					polish.push_back(opstack.top());
    					opstack.pop();
    				}
    				else
    				{
    					opstack.pop();
    					break;
    				}	
    			}
    			 
    		}
    		else/*加减乘除运算符*/
    		{
    			str1 = str[i];
    			while (!opstack.empty() && priority(opstack.top()) >= priority(str1))
    			{
    					polish.push_back(opstack.top());
    					opstack.pop();
    			}
    			opstack.push(str1); // 添加到符号栈中
    		}
    	}
    	//剩余的运算符添加到polish中
    	while (!opstack.empty())
    	{
    		polish.push_back(opstack.top());
    		opstack.pop();
    	}
    	return polish;
    }
    /*将逆波兰式进行计算*/
    int calculation(vector<string> polish)
    {
    	stack<int> data;
    	int a, b, c;
    	for (int i = 0; i < polish.size(); i++)
    	{
    		if (polish[i] == "+" || polish[i] == "-" || polish[i] == "*" || polish[i] == "/")
    		{
    			b = data.top(); data.pop();
    			a = data.top(); data.pop();
    			if (polish[i] == "+") c = a + b;
    			else if (polish[i] == "-") c = a - b;
    			else if (polish[i] == "*") c = a * b;
    			else if (polish[i] == "/") c = a / b;
    			data.push(c);
    		}
    		else
    		{
    			data.push(stoi(polish[i]));/*stoi函数功能:string to int */
    		}
    	}
    	return data.top();
    }
    
     

    测试结果:

    输入:string str = "1*(1+2*(1*2*2-3+5*1))";

    输出:13

    刷题检测网站

    如果想要练手,并检验是否正确,可以在Leetcode网站上检测一下

    leetcode-计算器

    题目和我的代码稍有不同  

     

     

     

    展开全文
  • 编译原理——逆波兰式分析计算

    千次阅读 2020-06-01 08:53:04
    将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式,并计算逆波兰式来表示的算术表达式的值。 二、实验说明 1、逆波兰式定义 将运算对象写在前面,而把运算符号写在后面。用这种表示法表示的...

    一、实验目的

    将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式,并计算用逆波兰式来表示的算术表达式的值。

    二、实验说明

    1、逆波兰式定义
    将运算对象写在前面,而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变,运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式,其优点在于易于计算机处理表达式。
    2、产生逆波兰式的前提
    中缀算术表达式
    3、逆波兰式生成的实验设计思想及算法

    (1)首先构造一个运算符栈,此运算符在栈内遵循越往栈顶优先级越高的原则。
    (2)读入一个用中缀表示的简单算术表达式,为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。
    (3)从左至右扫描该算术表达式,从第一个字符开始判断,如果该字符是数字,则分析到该数字串的结束并将该数字串直接输出。
    (4)如果不是数字,该字符则是运算符,此时需比较优先关系。
    做法如下:将该字符与运算符栈顶的运算符的优先关系相比较。如果,该字符优先关系高于此运算符栈顶的运算符,则将该运算符入栈。倘若不是的话,则将此运算符栈顶的运算符从栈中弹出,将该字符入栈。
    (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式,确定所有字符都得到正确处理,我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。
    3、逆波兰式计算的实验设计思想及算法

    (1)构造一个栈,存放运算对象。
    (2)读入一个用逆波兰式表示的简单算术表达式。
    (3)自左至右扫描该简单算术表达式并判断该字符,如果该字符是运算对象,则将该字符入栈。若是运算符,如果此运算符是二目运算符,则将对栈顶部的两个运算对象进行该运算,将运算结果入栈,并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符,则对栈顶部的元素实施该运算,将该栈顶部的元素弹出,将运算结果入栈。
    (4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式,确定所有字符都得到正确处理,我们便可以求出该简单算术表达式的值。

    三、实验环境

    Dev-C++

    四、实验要求

    (一)准备:
    1.阅读课本有关章节,
    2.考虑好设计方案;
    3.设计出模块结构、测试数据,初步编制好程序。
    (二)上课上机:
    将源代码拷贝到机上调试,发现错误,再修改完善。第二次上机调试通过。
    (三)程序要求:
    程序输入/输出示例:
    输出的格式如下:
    (1)逆波兰式的生成及计算程序,编制人:姓名,学号,班级
    (2)输入一以#结束的中缀表达式(包括+—/()数字#):在此位置输入符号串如4(28+876-75)/8
    (3)逆波兰式为:4&28&87&6
    +75-8/
    (4)逆波兰式test4&28&87&6
    +75-*8/=计算结果为237.5
    备注:(1)在生成的逆波兰式中如果两个数相连则用&分隔,如28和87,中间用&分隔;
    (2)在此位置输入符号串为用户自行输入的符号串。

    注意:1.表达式中允许使用运算符(±*/)、分割符(括号)、数字,结束符#;
    2.如果遇到错误的表达式,应输出错误提示信息(该信息越详细越好);
    3.对学有余力的同学,测试用的表达式事先放在文本文件中,一行存放一个表达式,同时以分号分割。同时将预期的输出结果写在另一个文本文件中,以便和输出进行对照;
    (四)程序思路
    模块结构:
    (1)定义部分:定义常量、变量、数据结构。
    (2)初始化:设立算符优先分析表、初始化变量空间(包括堆栈、结构体、数组、临时变量等);
    (3)控制部分:从键盘输入一个表达式符号串;
    (4)利用算符优先分析算法进行表达式处理:根据算符优先分析表对表达式符号串进行堆栈(或其他)操作,输出分析结果,如果遇到错误则显示错误信息。
    (5)对生成的逆波兰式进行计算。
    (五)练习该实验的目的和思路:
    程序较复杂,需要利用到程序设计语言的知识和大量编程技巧,逆波兰式的生成是算符优先分析法的应用,是一种较实用的分析法,通过这个练习可大大提高软件开发能力。
    (六)为了能设计好程序,注意以下事情:
    1.模块设计:将程序分成合理的多个模块(函数),每个模块做具体的同一事情。
    2.写出(画出)设计方案:模块关系简图、流程图、全局变量、函数接口等。
    3.编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。

    五、实验步骤

    #include<stdlib.h>
    #include<stdio.h>
    #include<math.h>
    #include<cstring>
    #define max 100
    void compvalue(char ex[max]);
    void trans(int p);
    int main(){
    	#ifdef ONLINE_JUDGE
    	#else
    		freopen("1.txt","r",stdin);         //文件读取本地文本内容 
    	#endif
    	int n;
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
    		trans(i);
    	}
        return 0;
    }
    /*将算术表达式转化为后缀表达式*/
    void trans(int p){        
    	char ex[max];          //存储后缀表达式
        char str[max];   	   //存储原算术表达式
        char stack[max];       //作为栈使用
        char ch;
        int sum,i,j,t,top=0;
        printf("*****************************************\n");
        printf("*请输入第%d个求值的表达式,以#结束。*\n",p+1);
        printf("******************************************\n");
        printf("算数表达式:");
        scanf("%s",str);		//获取用户输入的表达式
        printf("%s",str);
        sum=strlen(str);
        	i=0,t=0;
            ch=str[i];i++;
            while(ch!='#'){
                switch(ch){
    	            case '(':                 //判定为左括号
    	                top++;stack[top]=ch;
    	                break;
    	        	case ')':                 //判定为右括号
    	                while(stack[top]!='('){
    	                	ex[t]=stack[top];top--;t++;
    	                }
    	                top--;
    	                break;
    	        	case '+':                 	   //判定为加减号
    	                case '-':      
    	                    while(top!=0&&stack[top]!='('){
    	                        ex[t]=stack[top];top--;t++;
    	                    }
    	                    top++;stack[top]=ch;
    	                    break;
    	                case '*':                  //判定为乘除号
    	        		case '/':
    	                    while(stack[top]=='*'||stack[top]=='/'){
    	                        ex[t]=stack[top];top--;t++;
    	                    }
    	                    top++;stack[top]=ch;
    	                    break;
    	               case ' ':break;
    	               default:while(ch>='0'&&ch<='9'){                 //判定为数字
    	                       		ex[t]=ch;t++;
    	                       		ch=str[i];i++;
    	                    	}
    	                       i--;
    	                       ex[t]='&';t++;
                   }
                   ch=str[i];i++;
            }
            while(top!=0){
                ex[t]=stack[top];t++;top--;
            }
            ex[t]='#';
            printf("\n\t原来表达式:");
            for(j=0;j<sum;j++)
                printf("%c",str[j]);
        	printf("\n\t后缀表达式:",ex);
            for(j=0;j<t;j++)
                printf("%c",ex[j]);
        compvalue(ex);
    }
    /*计算后缀表达式的值*/
    void compvalue(char ex[max]){                                 
        float stack[max],d;             //作为栈使用
        char ch;
        int t=0,top=0;                  //t为ex下标,top为stack下标
        ch=ex[t];t++;
        while(ch!='#'){
            switch(ch){
                case '+':
                    stack[top-1]=stack[top-1]+stack[top];
                    top--;
                    break;
                case '-':
                    stack[top-1]=stack[top-1]-stack[top];
                    top--;
                    break;
                case '*':
                    stack[top-1]=stack[top-1]*stack[top];
                    top--;
                    break;
                case '/':
                    if(stack[top]!=0)
                        stack[top-1]=stack[top-1]/stack[top];
                    else{
                        printf("\n\t除零错误!\n");
                        exit(0);                   //异常退出
                    }
                    top--;
                    break;
                    default:
                    d=0;
                    while(ch>='0'&&ch<='9'){
                        d=10*d+ch-'0';               //将数字字符转化为对应的数值
                        ch=ex[t];t++;
                    }
                    top++;
                    stack[top]=d;
            }
            ch=ex[t];t++;
        }
        printf("\n\t计算结果:%g\n",stack[top]);
    }
    

    六、实验结果与讨论

    在这里插入图片描述
    文件读取的本地文本内容:
    在这里插入图片描述

    七、总结

    通过本次实验,我更清楚的理解了算符优先分析表,将中缀表达式转换为逆波兰式的过程,以及对逆波兰式的计算,通过文件读取方式将待计算的本地所有中缀表达式一一读取计算,打印出相对应的值。

    展开全文
  • 波兰式、逆波兰式与表达式求值

    万次阅读 多人点赞 2018-12-30 11:22:11
    波兰式、逆波兰式与表达式求值  《数据结构》中关于栈的解释经常会涉及到逆波兰式,波兰式,中缀式表达式的求值问题。但是,十分惭愧,整个大一阶段, 数据结构的课程没有上够5节,没有意识要学习,吃亏真的很大...

    波兰式、逆波兰式与表达式求值

      《数据结构》中关于栈的解释经常会涉及到逆波兰式,波兰式,中缀式表达式的求值问题。但是,十分惭愧,整个大一阶段,

    数据结构的课程没有上够5节,没有意识要学习,吃亏真的很大,只能现在恶补了。废话不说了,进入正题。

     

    1. 中缀表达式

           人类最熟悉的一种表达式1+2,(1+2)*3,3+4*2+4等等都是中缀表示法。对于人们来说,也是最直观的一种求值方式,先算括号里的,
    然后算乘除,最后算加减,但是,计算机处理中缀表达式却并不方便,因为没有一种简单的数据结构可以方便从一个表达式中间抽出
    一部分算完结果,再放进去,然后继续后面的计算(链表也许可以,但是,代价也是不菲)。
           在介绍前缀,后缀表达式之前,我想先通过我们最熟悉的中缀表达式画出一棵语法树来直观认识前后缀表达式。以A+B*(C-D)-E*F为例:

    则中缀表达式得名于它是由相应的语法树的中序遍历的结果得到的。

     

     

    2. 前缀缀表达式

     

      前缀表达式又叫做波兰式。同样的道理,表达式的前缀表达式是由相应的语法树的前序遍历的结果得到的。

    如上图的前缀表达式为- + A * B - C D * E F

    由前缀表达式求出结果有下面两种思路:

      1.从左至右扫描表达式,如果一个操作符后面跟着两个操作数时,则计算,然后将结果作为操作数替换(这个操作符和两个操作数),

    重复此步骤,直至所有操作符处理完毕。如-+A*B-CD*EF,扫描到-CD时,会计算C-D=C',表达式变成:-+A*BC'*EF

    继续扫描到*BC',计算B*C'=B',表达式变成:-+AB'*EF,继续+AB',依此类推。

      2.由1.知,要多遍扫描表达式,并且需要将3个字符替换成1个,比较繁锁,我们可以用一个栈S2来实现计算,扫描从右往左进行,

    如果扫描到操作数,则压进S2,如果扫描到操作符,则从S2弹出两个操作数进行相应的操作,并将结果压进S2(S2的个数出2个进1个),

    当扫描结束后,S2的栈顶就是表达式结果。

     

    3. 后缀表达式

      后缀表达式又叫做逆波兰式。它是由相应的语法树的后序遍历的结果得到的。如上图的后缀表达式为:

    A B C D - * + E F * -

    由前缀表达式求出结果十分方便,只需要用一个栈实现:

    我们可以用一个栈S2来实现计算,扫描从左往右进行,如果扫描到操作数,则压进S2,如果扫描到操作符,则从S2弹出两个操作数

    进行相应的操作,并将结果压进S2(S2的个数出2个进1个),当扫描结束后,S2的栈顶就是表达式结果。后缀表达式和前缀表达式看

    起来就像一对逆过程,实际上并不是这样子,因为字符读取的时候都是从左往右的,所以,前缀表达式往往需要用两个栈来计算,

    其中一个栈用来预处理:将字符串倒序压进栈中。

     

    4. 中缀表达式转换成后缀表达式

      既然中缀表达式对于计算机的运算并不便利,而前缀后缀表达式的计算相对简单方便。因此,找到一种途径将中缀表达式

    转换成前缀后缀表达式就十分重要。实际上,二者的转换算法看起来也很像一个逆过程。因此,我们着重讨论中缀转后缀。

    从理论上讲,已知一棵二叉树的中序遍历序列,要求出它的后序遍历序列是不唯一的,即文法是有多义性的。但是,在这

    里加上了优先级这一限制条件,转换就变得唯一了。

     

    算法:中缀表达式转换成后缀表达式

    输入:中缀表达式串

    输出:后缀表达式串

    PROCESS BEGIN:

       1.从左往右扫描中缀表达式串s,对于每一个操作数或操作符,执行以下操作;

                    2.IF (扫描到的s[i]是操作数DATA)

             将s[i]添加到输出串中;

                   3.IF (扫描到的s[i]是开括号'(')

                            将s[i]压栈;

                   4.WHILE (扫描到的s[i]是操作符OP)

                           IF (栈为空 或 栈顶为'(' 或 扫描到的操作符优先级比栈顶操作符高)

                                 将s[i]压栈;

                                 BREAK;

                           ELSE

                                 出栈至输出串中

                   5.IF (扫描到的s[i]是闭括号')')

                           栈中运算符逐个出栈并输出,直到遇到开括号'(';

                           开括号'('出栈并丢弃;

                   6.返回第1.步

             7.WHILE (扫描结束而栈中还有操作符)

                            操作符出栈并加到输出串中

    PROCESS END

     

    4. 中缀表达式转换成前缀表达式

      中缀表达式转换成前缀表达式和中缀表达式转换成后缀表达式十分类似,只需要将扫描方向由前往后变成由后往前,

    将'('改为')',')'改为'(',注意其中一个判断优先级的地方需要由>=变成>.

      至此,理论基础已经讲完了,用一道OJ题目来客观认识一下会比较好理解。HDU2127

    Polish notation

    Time Limit: 10000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 112    Accepted Submission(s): 32

    Problem Description

    Now, give you a string of standard arithmetic expressions, please tell me the Polish notation and the value of expressions.

    Input

    There're have multi-case. Every case put in one line, the expressions just contain some positive integers(all less than 100, the number of integers less than 20), bi-operand operators(only have 3 kinds : +,-,*) and some brackets'(',')'.
    you can assume the expressions was valid.

    Output

    Each case output the Polish notation in first line, and the result of expressions was output in second line.
    all of the answers are no any spaces and blank line.the answer will be not exceed the 64-signed integer.

    Sample Input

    
     

    1+2-3*(4-5) 1+2*(3-4)-5*6

    Sample Output

    
     

    Case 1: - + 1 2 * 3 - 4 5 6 Case 2: - + 1 * 2 - 3 4 * 5 6 -31

    Author

    威士忌

    Source

    HDU 2007-10 Programming Contest

     

    解释:

      网上很少这道题的题解,我先写一个吧,前面题目扯了一堆废话(我全删掉了),只有一句最重要的:给你中缀表达式,求出它的波兰式并计算出

    结果。题目是很裸的将中缀表达式转换成前缀表达式,再进行计算出结果,可以直接套上面的算法。但是,这里有一些点易错点需要注意:

         1.转化后的前缀表达式需要留一个空格

      2.因为数字并不是1位的,因为数字<100,有可能有两位,所以,不能只读取一个字符做为数字,需要读取所有的数字,具体看代码对数字的处理

      3.要注意有可能超过int的范围,一开始就想当然地用int,结果WA,还要注意将字符串转化为__int64

    #include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    char stack[500];					//定义顺序栈,其中top==0表示栈为空;
    int top;							//栈顶指针,为0表示栈为空;
    char output[500], input[500];		//波兰式
    int outLen;
    
    int priority(char op)				//判断运算符级别函数;其中* /的级别为2,+ -的级别为1;
    {
    	if (op=='+' || op=='-')
    		return 1;
    	if (op=='*' || op=='/')
    		return 2;
    	else
    		return 0;
    }
    
    bool isOperator(char op)				//判断输入串中的字符是不是操作符,如果是返回true
    {
    	return (op=='+' || op=='-' || op=='*' || op=='/');
    }
    
    void Polish(char *s,int len)			//将一个中缀串转换为前缀串,
    {
    	memset(output,'\0',sizeof output);	//输出串
    	outLen = 0;
    	for (int i=len-1; i >= 0; --i)		//1)求输入串的逆序。
    	{
    		if (isdigit(s[i]))				//经验见:http://blog.csdn.net/linraise/article/details/18566319#comments
    		{
    			output[outLen++] = s[i];	//3)假如是操作数,把它添加到输出串中。
    			while (i-1 >= 0 && isdigit(s[i-1]))
    			{
    				output[outLen++] = s[i-1];
    				--i;
    			}
    			output[outLen++] = ' ';		//空格隔开
    		}
    		if (s[i]==')')				    //4)假如是闭括号,将它压栈。
    		{
    			++top;
    			stack[top] = s[i];
    		}
    		while (isOperator(s[i]))		//5)如果是运算符,执行算法对应操作;
    		{												//>=很重要
    			if (top==0 || stack[top]==')' || priority(s[i]) >= priority(stack[top])) //空栈||或者栈顶为)||新来的元素优先级更高
    			{
    				++top;
    				stack[top] = s[i];
    				break;
    			}
    			else
    			{
    				output[outLen++] = stack[top];
    				output[outLen++] = ' ';
    				--top;
    			}
    		}
    		if (s[i]=='(')					//6)假如是开括号,栈中运算符逐个出栈并输出,直到遇到闭括号。闭括号出栈并丢弃。
    		{
    			while (stack[top]!=')')
    			{
    				output[outLen++] = stack[top];
    				output[outLen++] = ' ';
    				--top;
    			}
    			--top;	// 此时stack[top]==')',跳过)
    		}
    		//7)假如输入还未完毕,跳转到步骤2。
    	}
    	while (top!=0)						//8)假如输入完毕,栈中剩余的所有操作符出栈并加到输出串中。
    	{
    		output[outLen++] = stack[top];
    		output[outLen++] = ' ';
    		--top;
    	}
    }
    
    char DstBuf[200];
    char* OP(char* op1,char* op2,char op)
    {
    	__int64 res = 0;
    	if (op=='+')
    		res = _atoi64(op1) + _atoi64(op2);
    	else if (op=='-')
    		res = _atoi64(op1) - _atoi64(op2);
    	else if (op=='*')
    		res = _atoi64(op1) * _atoi64(op2);
    	else if (op=='/')
    		res = _atoi64(op1) / _atoi64(op2);
    	_i64toa(res,DstBuf,10);
    	return DstBuf;
    }
    
    char cSt1[200][80], cSt2[200][80];
    __int64 calc(char *s)				//波兰式需要用两个栈,逆波兰式只需要一个栈
    {
    	int top1=0, top2=0, i;
    	for (i=0; s[i]; ++i)
    	{
    		if (s[i] && s[i] != ' ')
    		{
    			++top1;
    			sscanf(s+i,"%s",cSt1[top1]);		//初始化其中一个栈
    			while (s[i] && s[i] != ' ')
    				++i;
    		}
    	}
    	while (top1 != 0)	//栈不空
    	{
    		if (!isdigit(cSt1[top1][0]))	//是操作符
    		{
    			OP(cSt2[top2], cSt2[top2-1], cSt1[top1][0]);
    			memcpy(cSt2[top2-1],DstBuf,sizeof DstBuf);
    			--top2;						//操作数栈:出栈俩,进栈一
    			--top1;						//操作符出栈
    		}
    		else
    		{
    			++top2;						//数进操作数栈
    			memcpy(cSt2[top2],cSt1[top1],sizeof cSt1[top1]);
    			--top1;						//操作符出栈
    		}
    	}
    	return _atoi64(cSt2[1]);
    }
    int main()
    {
    #ifndef ONLINE_JUDGE
    	freopen("2.txt","r",stdin);
    #endif
    
    	int T = 1;
    	while (gets(input))
    	{
    		Polish(input, strlen(input));
    		reverse(output,output+outLen-1);
    		output[outLen-1] = '\0';
    		printf("Case %d:\n%s\n",T++,output);
    		printf("%I64d\n",calc(output));
    	}
    	return 0;
    }

    做完了波兰式,再看一个逆波兰式的题:HDU1237
    这道是裸的逆波兰,只是简化版本的,我用上面的算法往上一交,结果WA,测试了一下这个用例1 - 3 + 4,结果输出-6,显然是优先级顺序没有处理好,

    改了一下prirority就行了

    更简单的做法可以看这里,本质上是简化了的逆波兰式解法。

    #include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    char stack[500];					//定义顺序栈,其中top==0表示栈为空;
    int top;							//栈顶指针,为0表示栈为空;
    char output[500], input[500];		//波兰式
    int outLen;
    
    int priority(char op)				//判断运算符级别函数;其中* /的级别为2,+ -的级别为1;
    {
    	if (op=='+' || op=='-')
    		return 1;
    	if (op=='*' || op=='/')
    		return 2;
    	else
    		return 0;
    }
    
    bool isOperator(char op)				//判断输入串中的字符是不是操作符,如果是返回true
    {
    	return (op=='+' || op=='-' || op=='*' || op=='/');
    }
    
    void rePolish(char *s,int len)			//将一个中缀串转换为后缀串,
    {
    	memset(output,'\0',sizeof output);	//输出串
    	outLen = 0;
    	for (int i=0; i < len; ++i)			//1)求输入串的逆序。
    	{
    		if (isdigit(s[i]))				//经验见:http://blog.csdn.net/linraise/article/details/18566319#comments
    		{
    			output[outLen++] = s[i];		//3)假如是操作数,把它添加到输出串中。
    			while (i+1 < len && isdigit(s[i+1]))
    			{
    				output[outLen++] = s[i+1];
    				++i;
    			}
    			output[outLen++] = ' ';		//空格隔开
    		}
    		if (s[i]=='(')					//4)假如是闭括号,将它压栈。
    		{
    			++top;
    			stack[top] = s[i];
    		}
    		while (isOperator(s[i]))		//5)如果是运算符,执行算法对应操作;
    		{
    			if (top==0 || stack[top]=='(' || priority(s[i]) > priority(stack[top])) //空栈||或者栈顶为)||新来的元素优先级更高
    			{
    				++top;
    				stack[top] = s[i];
    				break;
    			}
    			else
    			{
    				output[outLen++] = stack[top];
    				output[outLen++] = ' ';
    				--top;
    			}
    		}
    		if (s[i]==')')					//6)假如是开括号,栈中运算符逐个出栈并输出,直到遇到闭括号。闭括号出栈并丢弃。
    		{
    			while (stack[top]!='(')
    			{
    				output[outLen++] = stack[top];
    				output[outLen++] = ' ';
    				--top;
    			}
    			--top;	// 此时stack[top]==')',跳过)
    		}
    		//7)假如输入还未完毕,跳转到步骤2。
    	}
    	while (top!=0)						//8)假如输入完毕,栈中剩余的所有操作符出栈并加到输出串中。
    	{
    		output[outLen++] = stack[top];
    		output[outLen++] = ' ';
    		--top;
    	}
    }
    
    double OP(double op1,double op2,char op)
    {
    	double res = 0;
    	if (op=='+')
    		res = op1 + op2;
    	else if (op=='-')
    		res = op1 - op2;
    	else if (op=='*')
    		res = op1 * op2;
    	else if (op=='/')
    		res = op1 / op2;
    	return res;
    }
    
    double cSt1[200];
    double calc(char *s)				//波兰式需要用两个栈,逆波兰式只需要一个栈
    {
    	char dst[80];
    	int top1=0, i;
    	for (i=0; s[i]; ++i)
    	{
    		if (s[i] && s[i] != ' ')
    		{
    			sscanf(s+i,"%s",dst);
    			if (isdigit(dst[0]))
    			{
    				++top1;
    				cSt1[top1] = atof(dst);		//进栈
    			}
    			else
    			{
    				cSt1[top1-1] = OP(cSt1[top1-1], cSt1[top1], dst[0]);
    			//	memcpy(cSt1[top1-1],DstBuf,sizeof DstBuf);
    				--top1;						//操作数栈:出栈俩,进栈一
    			}
    			while (s[i] && s[i] != ' ')
    				++i;
    		}
    	}
    	return cSt1[1];
    }
    int main()
    {
    #ifndef ONLINE_JUDGE
    	freopen("2.txt","r",stdin);
    #endif
    
    	int T = 1;
    	while (gets(input) && strcmp(input,"0"))
    	{
    		rePolish(input, strlen(input));
    
    		output[outLen-1] = '\0';
    //		printf("Case %d:\n%s\n",T++,output);
    		printf("%.2lf\n",calc(output));
    	}
    	return 0;
    }
    //测试用例:1 - 3 + 4


     

    展开全文
  • 逆波兰式的产生与计算

    万次阅读 2016-06-26 20:16:30
    生成逆波兰式流程图:逆波兰式计算流程图:要求:可以区分小数点、多次幂、正负号代码:#include #include #include #include #include #include using namespace std;char str[50]; //用于存放原来的表达式
  • 表达式计算 - 逆波兰式转换及运算示例自定义表达式运算中,涉及到三个步骤: 1.关键字析取 2.中序表达式转逆波兰表达式 3.逆波兰表达式运算。 本实现基于C#,可生成对象化的中序表达式和逆波兰表达式,可处理...
  • 计算逆波兰式

    2016-12-26 14:50:00
    中缀表达式(a+b)*c-(a+b)/e的逆波兰式是ab+c*ab+e/-。   逆波兰表达式是一种利用栈来进行运算的数学表达式。 以一个表达式 1 + 2 * 3 为例。 以顺序方式输入这个表达式,计算机首先需要解析这个表达式,...
  • 在栈的应用 - 波兰式与逆波兰式中,借助于栈,实现了中缀表达式到前缀表达式和后缀表达式的转换。   正如已经提到的,因为此前在实现栈的时候,栈的元素类型elementType是通过typedef来指定的,这样虽然也可以根据...
  • 前缀,中缀,后缀表达式(逆波兰表达式) 参考: https://www.cnblogs.com/chensongxian/p/7059802.html 中缀表达式 中缀表达式就是常见的运算表达式,如 (3 + 4) * 5 - 6 前缀表达式 介绍 前缀表达式又称为波兰式,...
  • 逆波兰式的转换与计算(简单)

    万次阅读 2018-09-18 21:25:16
    输入有两行,第一行为逆波兰式的结果,第二行为输入表达式的正确计算结果。逆波兰式中相邻的数字或运算符之间不用输出空格 保证表达式计算的合理性,不需判断除零等情况 表达式的计算遵循同级运算从左向右,先乘除后加...
  • 相对完善的代码请见另一篇博客--完整的逆波兰式计算,修正了函数嵌套时出现的问题,调整的一定的 处理方式,使得代码更加简洁。不过大体思路与本代码基本相同。 //本代码提供的测试数据 //9.4+(3.27-1.05)*3.44+10...
  • 计算逆波兰式(后缀表达式)的值 题目描述 计算逆波兰式(后缀表达式)的值 运算符仅包含"+","-","“和”/",被操作数可能是整数或其他表达式 例如: [“2”, “1”, “+”, “3”, ""] -> ((2 + 1) * 3) -> 9...
  • 逆波兰式转换

    2019-03-22 10:35:36
    2、输出:逆波兰式以及计算结果 转换过程如下所示: 栈底放‘#’,从左至右逐字读取中缀式: a.当当前字符为数字时,直接输出; b.当当前字符为"(“时,将其压栈; c.当当前字符为”)“时,则弹出堆栈中最上的”(...
  • 文章目录波兰式和逆波兰式波兰式表示法(PN):中缀表达式转换成前缀表达式PN思路PN实现逆波兰表示法(RPN):中缀表达式转后缀表达式RPN思路RPN实现 波兰式和逆波兰式 波兰式 逆波兰式 中缀表达式 定义 在...
  • 编译原理 —— 逆波兰式

    千次阅读 2019-05-12 21:05:29
    逆波兰式表示表达式的最大优点是易于计算处理。 逆波兰式只使用一个工作栈,当计算机自左向右顺序扫描逆波兰式时,若当前符号是运算对象则进栈,若当前符号是运算符,并且为K元运算符,则将栈顶的K个元素依次取出...
  • 波兰式与逆波兰式

    千次阅读 2018-08-11 10:59:19
    一、波兰式(前缀表达式) 波兰式是在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之前,所以,这种表示法也称为前缀表达式。例如:3*(2-(5+1)),用波兰式来表示是:* 3 - 2 + 5 1。 阅读这个...
  • 根据中缀表达式计算后缀表达式 https://blog.csdn.net/lcl497049972/article/details/83061274 中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9 3 1-3*+ 10 2/+” 规则:从左到右遍历中缀表达式的每个数字和...
  • 波兰式 和 逆波兰式

    2013-02-02 13:08:00
    逆波兰式又称后缀式 还有一个前缀式 中缀式: 根据算符间的优先关系来确定运算的次序,此外,还应顾及括号规则 如 (A+B)*(C+D) = 运算法则符合我们正常的运算规律 后缀式是有中缀式所得 如 AB+CD+* ...
  • js实现 - 逆波兰式

    2019-05-26 16:52:00
    最近编译原理实验有涉及到逆波兰式,而且听闻有人在前端面试过程中被问到逆波兰式算法的实现,之前的离散数学课程中也有涉及到逆波兰式,作为一名前端人员,终于按耐不住想用js去实现求逆波兰式的算法。我查阅了大量...
  • 逆波兰式计算器实现

    2021-06-17 17:50:23
      逆波兰计算器的计算过程为:从左到右扫描后缀表达式,遇到数字就入栈,遇到操作符就从栈弹出两个数字,然后计算得到的值继续入栈,继续扫描表达式,直到扫描完毕得到结果。   从逆波兰计算器的扫描过程可以...
  • 波兰式,逆波兰式

    千次阅读 2012-04-30 23:17:38
    2、逆波兰式(后缀式)计算机看来却是比较简单易懂的结构,因为计算机普遍采用的内存结构是栈式结构,它执行先进后出的顺序。 3、前缀式 1、中缀式:根据算符间的优先关系来确定运算的次序,此外,还应顾及括号规则...
  • 但是机器是不喜欢中缀式,它更喜欢后缀式,也就是逆波兰式逆波兰式的理解: 1.逆波兰式: ab35c-x+= 2.计算机计算过程: 策略:计算机从左到右进行扫描,遇到操作数入栈,遇到运算符,最靠近栈顶的两个...
  • 引入波兰式与逆波兰式: 一个式子,可以分成几个层面来看。比如1 + 2 * 3,我们看它是个算式,计算机看它,那就是个字符串,所以首先必须把它拆分成计算机可以操作的数据单元,就是Tokenize。比如1 2 3是操作数,+ ...
  • 计算器逆波兰式图解

    2020-04-13 11:19:22
    波兰式转逆波兰式 首先是总体步骤 首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为输入逆波兰式的栈S2(空栈),S1栈可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的...
  • 文章目录一、前言二、表达式1.中缀表达式1.1 定义2.前缀表达式2.1 定义2.2 求值3....逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,276
精华内容 910
关键字:

逆波兰式计算过程