C/C++ 编程—简单计算器栈、队列、map

╰+哭是因爲堅強的太久メ 2023-02-19 15:26 74阅读 0赞

[1918-ProblemA-简单计算器][1918-ProblemA-]

题目描述  
读入一个只包含 +, -, \*, / 的非负整数计算表达式，计算该表达式的值。

输入  
测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。

输出  
对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。

样例输入 Copy

30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 * 6 + 51 / 29 + 79 * 87 + 57 * 92
    0

样例输出 Copy

12178.21

思路：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70 1]

//1918-ProblemA-简单计算器--法2 
    /* 中缀转后缀，计算后缀表达式 步骤一：中缀表达式转后缀表达式 设立一个操作符栈，用以临时存放操作符，根据要求将符合要求的操作符从栈顶弹出到后缀表达式中； 设立一个数组或队列，用以存放后缀表达式。从左到右扫描中缀表达式，如果遇到操作数， 就把操作数加入后缀表达式中；如果遇到操作符，根据后缀表达式的特性，就将其操作符与操作符栈 的栈顶操作符的优先级比较：如果高于栈顶元素的优先级，则压入操作符栈；若低于或等于，则将操作符栈的栈顶元素不断弹出到后缀表达式中， 直到其优先级大于栈顶元素。重复以上操作，直到中缀表达式扫描完毕，之后将操作符栈剩余的操作符依次弹入到后缀表达式中。 步骤二： 计算后缀表达式 从左到右扫描后缀表达式，如果是操作数，则入栈；如果是操作符，则连续弹出两个操作数， 然后进行操作符的操作生成的新操作数压入栈中，直到后缀表达式扫描完毕，最终答案就是栈中最后一个元素。 */
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <queue>
    #include <cstdlib>
    #include <stack>
    #include <map>
    #include <string>
    using namespace std;
    
    struct node{ 
    	double num;//数字 
    	char op;//操作符 
    	bool flag;//区分数字（1）操作符（0） 
    }; 
    string str;
    stack<node> s;//操作符栈
    queue<node> q;//后缀表达式队列
    map<char,int> opp;//操作符优先级映射
    void change(){ //中缀表达式转后缀表达式
    	double num;
    	node temp;
    	int len = str.length();
    	for(int i=0;i<len; ){ 
    		if(str[i] >= '0' && str[i] <= '9'){ 
    			temp.flag = 1;
    			temp.num = str[i++] - '0';//读取这个操作数的首位 
    			while(i< len && str[i] >= '0' && str[i] <= '9'){ //读取这个操作数 
    				temp.num = temp.num * 10 + (str[i] - '0');
    				i++;
    			}
    			q.push(temp);
    		}
    		else{ //操作符 
    			temp.flag = 0;
    //若低于或等于，则将操作符栈的栈顶元素不断弹出到后缀表达式中，
    //直到其优先级大于栈顶元素
    			while(!s.empty() && opp[str[i]] <= opp[s.top().op]){ 
    				q.push(s.top());
    				s.pop();
    			}
    			//如果高于栈顶元素的优先级，则压入操作符栈
    			temp.op = str[i];
    			s.push(temp);
    			i++;
    		}
    	} 
    	//如果操作符栈中还有操作符，就把它弹出到后缀表达式队列中
    	while(!s.empty()){ 
    		q.push(s.top());
    		s.pop();
    	}
    } 
    //计算后缀表达式
    double cal(){ 
    	double temp1,temp2;
    	node cur,temp;
    	while(!q.empty()){ //后缀表达式非空 
    		cur = q.front();//cur暂存队首元素 
    		q.pop();
    		if(cur.flag == 1)	s.push(cur);//操作数入栈
    		else{ //操作符
    			temp2 = s.top().num;//弹出栈顶第一操作数
    			s.pop();
    			temp1 = s.top().num;//弹出第二操作数 
    			s.pop();
    			temp.flag = 1;//临时记录操作数
    			if(cur.op == '+')	temp.num = temp1 + temp2;//加法
    			else if(cur.op == '-')	temp.num = temp1 - temp2;
    			else if(cur.op == '*')	temp.num = temp1 * temp2;
    			else	temp.num = temp1 / temp2;
    			s.push(temp);//将计算结果压入栈 
    		} 
    	}
    	return s.top().num;//最终数字栈最后一个数即结果 
    } 
    
    
    int main() { 
    	opp['+'] = opp['-'] = 1;//设定操作符优先级
    	opp['*'] = opp['/'] = 2;
    	while(getline(cin,str),str != "0"){ 
    		for(string::iterator it = str.end();it!=str.begin();it--){ 
    			if(*it == ' ')	str.erase(it);//去掉表达式中的空格 
    		}
    		while(!s.empty())	s.pop();//初始化栈
    		change();
    		printf("%.2lf\n",cal());//计算后缀表达式的值 
    	} 
    	return 0;
    }

[1918-ProblemA-]: http://codeup.cn/problem.php?cid=100000605&pid=0
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200621143029457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200621143039465.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3,size_16,color_FFFFFF,t_70