蓝桥杯试题 算法训练 表达式计算-简易科学计算器-逆波兰算法

---

一、题目描述

一、资源限制
时间限制：1.0s 内存限制：256.0MB
二、问题描述
　　输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。
输入格式
　　输入一行，包含一个表达式。
输出格式
　　输出这个表达式的值。
样例输入
1-2+3*(4-5)
样例输出
-4
数据规模和约定
　　表达式长度不超过100，表达式运算合法且运算过程都在int内进行。

---

二、思路解析

1.因为数字都是int型并且大小在100以内，所以不需要考虑小数点和大数情况，简单了很多。
2.运用逆波兰算法，算出后缀表达式，对后缀表达式进行求解。
3.注意负号是作为符号还是运算符的判断。
4.如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+
(a+b)c-(a+b)/e的后缀表达式为：
(a+b)c-(a+b)/e
→((a+b)c)((a+b)/e)-
→((a+b)c)((a+b)e/)-
→(ab+c)(ab+e/)-
→ab+cab+e/-

三、逆波兰算法解析

逆波兰思路步骤：
1.转换为后缀表达式
首先需要分配1个栈，一个string串（以下称为str），一个作为临时存储运算符的栈S1（含一个结束符号），str用来存放逆波兰式，S1栈可先放入优先级最低的运算符#。从中缀式的左端开始取字符，逐序进行如下步骤：

（1）若取出的字符是操作数，则将该操作数直接送入str，每个数前后需要加上特殊符号分割，防止数字之间连写，如:$12$$3$。
（2）若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符（包括左括号）优先级，则将该运算符进S1栈，否则，将S1栈的栈顶直到‘#’或者‘（’的运算符全部弹出，送入str中，最后将该运算符送入S1栈。
（3）若取出的字符是“（”，则直接送入S1栈顶。
（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
（5）重复上面的1~4步，直至处理完所有的输入字符。
（6）若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入str。得到后缀表达式


2.对后缀表达式进行解析
（1）开辟新栈S2,若取出的字符是$,则提取出整个数字，压入栈S2。
（2）若取出的字符是运算符，则取出S2栈顶的两个数字进行该运算符的运算，将结果压入栈S2顶部。
（3）重复以上步骤，直到后缀表达式结束。
（4）取出栈S2顶部数字，即为最终结果。

四、直接上代码

代码如下（示例）：

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
int priority(char a){//判断优先级 
	if(a=='+'||a=='-')
		return 1;
	else
		if(a=='*'||a=='/')
			return 2;
		else
			if(a=='('||a=='#')
			 return 0;
}
int getnum(string a,int i){//如果碰到数字，获得数字最后一位的下一位位置，例如，1+24/3，若初始i为2的位置，则返回的i为/的位置 
	while(a[i]-'0'>=0&&a[i]-'0'<=9){
		i++;
	}
	return i;
}
int toint(string a){//将string转换为int 
	int num=0;
	for(int i=0;i<a.length();i++){
		int temp=a[i]-'0';
		num=num*10+temp;
	}
	return num;
}
int main(){
	string a;
	cin>>a;
	stack<char> c;
	c.push('#');
	string rev="";
	for(int i=0;i<a.length();i++){//预处理负号，-x变为0-x 
		if(a[i]=='-'){
			if(i==0||a[i-1]=='('){
				a.insert(i,"0");
			}
		}
	}
	for(int i=0;i<a.length();i++){//转换后缀表达式 
		char t=a[i];
		if(t-'0'>=0&&t-'0'<=9){//
			int next=getnum(a,i);//获取数的下一个位置 
			string temp=a.substr(i,next-i);//截取出数字 
			i=next-1;//i跳转到数字最后一位 
			rev+='$';//标记数字，两个$之间即为数字 
			rev+=temp;
			rev+='$';
		}
		else
		if(t=='('){ 
			c.push(t);
		}
		else
		if(t==')'){
			while(c.top()!='('){
				rev+=c.top();
				c.pop();
			}
			c.pop();//弹出（ 
		}
		else
		if(t=='+'||t=='-'||t=='*'||t=='/'){
			if(priority(t)>priority(c.top())){
				c.push(t);
			}
			else
			{
				while(c.top()!='#'&&c.top()!='('){
					rev+=c.top();
					c.pop();
				}
				c.push(t);
			}
		}
		if(i+1==a.length()){//将栈中剩下的符号弹出放入后缀表达式 
			while(c.top()!='#'){
				rev+=c.top();
				c.pop();
			}
		}
	}
	stack<long long int> n;
	for(int i=0;i<rev.length();i++){
		char t=rev[i];
		if(t=='$'){//提取数字，放入栈备用 
			string temp="";
			i++;
			while(rev[i]!='$'){
				temp+=rev[i];
				i++;
			}
			int num=toint(temp);
			n.push(num);
		}
		else
		if(t=='+'||t=='-'||t=='*'||t=='/'){
			int f=n.top();
			n.pop();
			int s=n.top();
			n.pop();
			if(t=='+')
				n.push(f+s);
			else
				if(t=='-')
					n.push(s-f);
				else
					if(t=='*')
						n.push(s*f);
					else
						if(t=='/')
							n.push(s/f);
		}
	} 
	cout<<n.top();
} 

代码在蓝桥杯官网已经通过

总结

了解逆波兰算法，同时也要注意细节方面，例如负号是作为符号还是运算符的判断。
大家的点赞就是我的动力！

---