栈的运用--中缀表达式求值（只有圆括号）

柔光的暖阳◎ 2021-07-16 11:14 344阅读 0赞

### 栈的运用–中缀表达式求值（只有圆括号） ###

# 题目描述 #

中缀表达式是我们熟悉的表达式形式。为了能正确表示运算的先后顺序，中缀表达式中难免要出现括号。假设我们的表达式中只允许有圆括号。  
读入一个浮点数为操作数的中缀表达式后，对该表达式进行运算。  
要求中缀表达式以一个字符串的形式读入，可含有加、减、乘、除运算符和左、右括号，并假设该表达式以“\#”作为输入结束符。  
如输入“3.5\*(20+4)-1\#”，则程序运行结果应为83。  
要求可单步显示输入序列和栈的变化过程。并考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。

# 结果预览 #

![在这里插入图片描述][20201006200855179.png_pic_center]

# 源码 #

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<sstream>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e5 + 5;
    const int Mod = 1e9 + 5;
    
    class stack
    { 
    public:
    	void push(char t) 
    	{ 
    		if (t == Max) {  cout << "溢出";return; }
    		data[++length] = t;
    	}
    	void pop()
    	{ 
    		if (length == 0) { cout << "溢出";return;}
    		length--;
    	}
    	char gettop() {  return data[length]; }
    	int getlength() {  return length; }
    
    private:
    	int data[Max];
    	int length = 0;
    };
    
    int be_number(string str)
    { 
    	stringstream sin;
    	int i = 0, d = -1e9 + 5, l = 0, r = 0;
    	double a = 0, b = 0;
    	while(i<str.size())
    	{ 
    		if (str[i] == '+'|| str[i] == '*' || str[i] == '/' || (str[i] == '-' && !(str[i + 1] <= '9' && str[i + 1] >= '0'))) {  cout << "错误：运算符操作有误" << endl;return -1e9 + 5; }
    		if (str[i] == '-') l = i++;
    		while ((str[i] <= '9' && str[i] >= '0')||str[i]=='.') i++;
    		sin << str.substr(l, i - l);
    		sin >> a;
    		if (i == str.size())return a;
    		if ((str[i] == '+' ||str[i] == '*' || str[i] == '/') && (str[i+1]!='-'&&(str[i + 1] > '9' || str[i + 1] < '0')))
    		{ 
    			cout << "错误：运算符操作有误" << endl;
    			return -1e9 + 5;
    		}
    		d = i;
    		l = ++i;
    		if (str[i] == '-')i++;
    		while ((str[i] <= '9' && str[i] >= '0')||str[i]=='.') i++;
    		sin.clear();
    		sin << str.substr(l, i - l);
    		sin >> b;
    		if (str[d] == '+') a= a + b;
    		else if (str[d] == '-') a= a - b;
    		else if (str[d] == '*') a= a * b;
    		else if (str[d] == '/') a= a / b;
    		string ss;sin.clear();sin << a;sin >> ss;
    		str.replace(0, i, ss);i = 0;l = 0;
    	}
    
    }
    
    void project()
    { 
    	cout << "请输入表达式并于尾部加#作为结束标志" << endl;
    	string str;
    	cin >> str;
    	str = str.substr(0, str.size() - 1);
    	stack sta;
    	stringstream sin;string ss;
    	for (int i = 0;i < str.size();i++)
    	{ 
    		if (str[i] == '(')sta.push(i);
    		else if (str[i] == ')')
    		{ 
    			if (sta.getlength() == 0) {  cout << "错误：右括号无匹配";return; }
    			double t = be_number(str.substr(sta.gettop()+1, i - sta.gettop()-1));
    			if (t == -1e9 + 5)return;
    			sin.clear();sin << t;sin >> ss;
    			str.replace(str.find(str.substr(sta.gettop(), i - sta.gettop() + 1)), i - sta.gettop() + 1, ss);
    			cout << str << " 目前栈中左括号数量为" << sta.getlength()-1 << endl;
    			i = sta.gettop() + ss.size() - 1;
    			sta.pop();
    		}
    	}
    	if (sta.getlength() != 0)cout << "错误：左括号剩余" << endl;
    	else if (be_number(str) != -1e9 + 5)cout << be_number(str);
    }
    
    int main()
    { 
    	project();
    }

[20201006200855179.png_pic_center]: /images/20210716/c30df5e62f9c4e019fe19e2a95d6c8ce.png