数据结构实验二：栈和队列的算法

青旅半醒 2022-12-23 01:57 157阅读 0赞

实验要求  
1、表达式求值（完成书中P53页算法3.4）；  
2、实验报告格式及图表清晰；  
3、如有雷同，均算抄袭，按零分处理。  
**代码：**

#include<iostream>
    #include<stack>
    #include<cstring>
    
    using namespace std;
    using ll = double;
    
    char op[7][7] = {
         // + - * / ( ) #
    	'>','>','<','<','<','>','>',
    	'>','>','<','<','<','>','>',
    	'>','>','>','>','<','>','>',
    	'>','>','>','>','<','>','>',
    	'<','<','<','<','<','=',' ',
    	'>','>','>','>',' ','>','>',
    	'<','<','<','<','<',' ','='
    };
    
    char Precede(char a, char b) {
        
    	int i = 0, j = 0;
    	string p = "+-*/()#";
    	for (int k = 0; k < p.size(); k++) {
        
    		if (a == p[k]) i = k;
    		if (b == p[k]) j = k;
    	}
    	return op[i][j];
    }
    
    ll Operate(ll a, char x, ll b) {
        
    	switch (x)
    	{
        
    	case '+':
    		return a + b;
    	case '-':
    		return a - b;
    	case '*':
    		return a * b;
    	case '/':
    		if (b == 0 && a > 0) {
        
    			return DBL_MAX;
    		}
    		else if (b == 0 && a < 0) {
        
    			return -DBL_MAX;
    		}
    		else if(b == 0 && a == 0){
        
    			return 1;
    		}
    		else return a / b;
    	default:
    		break;
    	}
    }
    
    bool in(char c) {
        
    	string p = "+-*/()#";
    	int len = p.size();
    	for (int i = 0; i < len; i++) {
        
    		if (c == p[i]) return true;
    	}
    	return false;
    }
    
    ll Jisuanqi(string s)
    {
        
    	stack<ll> st1;
    	stack<char> st2;
    	st2.push('#');
    	char x;
    	ll a, b;
    	for (int i = 0; i < s.size(); i++) {
        
    		if ((s[i] > '9' || s[i] < '0') && !in(s[i])) {
        
    			cout << "输入错误，返回代码：";
    			return 0;
    		}
    		int sign = 1;
    		if ((i == 0 || s[i-1] == '(') && s[i] == '-') {
        
    			sign = -1;
    			i++;
    		}
    		if (s[i] <= '9' && s[i] >= '0') {
        
    			ll ans = 0;
    			while ((s[i] <= '9' && s[i] >= '0' || s[i] == '.') && i < s.size()) {
        
    				if (s[i] == '.') {
        
    					i++;
    					ll cnt = 0;
    					int flag = 1;
    					while (s[i] <= '9' && s[i] >= '0' && i < s.size()) {
        
    						cnt *= 10;
    						cnt += (ll)s[i] - '0';
    						i++;
    						flag *= 10;
    					}
    					ans += cnt / flag;
    				}
    				else {
        
    					ans *= 10;
    					ans += (ll)s[i] - '0';
    					i++;
    				}
    			}
    			ans *= sign;
    			st1.push(ans);
    			i--;
    		}
    		else {
        
    			switch (Precede(st2.top(), s[i])) {
        
    			case '<':
    				st2.push(s[i]);
    				break;
    			case '=':
    				st2.pop();
    				break;
    			case '>':
    				x = st2.top();
    				st2.pop();
    				b = st1.top();
    				st1.pop();
    				a = st1.top();
    				st1.pop();
    				st1.push(Operate(a, x, b));
    				i--;
    				break;
    			}
    		}
    	}
    	return st1.top();
    }
    
    int main()
    {
        
    	string s;
    	while (true) {
        
    		cin >> s;
    		s += '#';
    		ll ans = Jisuanqi(s);
    		cout << ans << endl;
    	}
    }