2 solutions

  • 0
    @ 2022-2-10 14:26:18

    这种运算题的基本原理和中缀表达式转换后缀表达式是一样的,但是各种细节很需要注意一下。(什么叫代码10分钟,bug一小时啊)

    思路: 开两个栈,一个储存数字,一个储存计算符,遍历表达式,如果是数字就直接入数字栈,如果是计算符,就判断符号栈中已有符号的优先级,将所有优先级比其高或者一样的符号出栈,每出栈一个符号,就拿数字栈的2个栈顶元素来进行计算,然后答案再入栈,直到空栈或者符号栈顶元素优先级比其低,再将这个计算符入栈。遍历完表达式后,如果符号栈还没空,就挨个出栈,再利用数字栈计算:取两个栈顶元素出来,再塞个答案回去。直到栈空,数字栈的唯一一个元素就是答案了。

    #include <bits/stdc++.h>
    #include <stack>
    using namespace std;
    
    
    int main() {	
    	int t;
    	cin >> t;
    	getchar();
    	while (t--) {
    		stack<double> S1;//数字栈
    		stack<char> S2;//符号栈
    		string s;
    		double u = 0;
    		getline(cin, s);
    		int len = s.length();
    		for (int i = 0; i < len; i++) {
    			if (s[i] - '0' >= 0 && s[i] - '0' <= 9) { // 注意读取字符串数字的方式
    				u = 0;
    				while (s[i] - '0' >= 0 && s[i] - '0' <= 9) {
    					u = u * 10 + (s[i] - '0');
    					i++;
    				}
    				S1.push(u);
    			}		
    			else if (s[i] == '+' || s[i] == '-') {
    				while (!S2.empty()) {
    					double x, y;
    					y = S1.top();
    					S1.pop();
    					x = S1.top();
    					S1.pop();
    					if (S2.top() == '+') S1.push(x + y);
    					else if (S2.top() == '-') S1.push(x - y);
    					else if (S2.top() == '*') S1.push(x * y);
    					else if (S2.top() == '/') S1.push(x / y);
    					S2.pop();
    				}
    				S2.push(s[i]);
    			}
    			else if (s[i] == '*' || s[i] == '/') {
    				while (!S2.empty()) {
    					double x, y;
    					if (S2.top() == '+' || S2.top() == '-') break; //break一定要在数字栈元素出栈之前
    					y = S1.top();
    					S1.pop();
    					x = S1.top();
    					S1.pop();
    					if (S2.top() == '*') S1.push(x * y);
    					else if (S2.top() == '/') S1.push(x / y);
    					S2.pop();
    				}
    				S2.push(s[i]);
    			}
    	 }
    		while (!S2.empty()) {
    					double x, y;
    					y = S1.top();
    					S1.pop();
    					x = S1.top();
    					S1.pop();
    					if (S2.top() == '+') S1.push(x + y);
    					else if (S2.top() == '-') S1.push(x - y);
    					else if (S2.top() == '*') S1.push(x * y);
    					else if (S2.top() == '/') S1.push(x / y);
    					S2.pop();	
    	    }
    	printf("%.2lf\n",S1.top());
        }
        return 0;
    }
    

    Information

    ID
    1526
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    80
    Accepted
    17
    Uploaded By