CH1802 表达式计算4

描述

给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值

数据可能会出现括号情况，还有可能出现多余括号情况

数据保证不会出现>=2^31的答案

数据可能会出现负数情况

输入格式

仅一行，即为表达式

输出格式

仅一行，既为表达式算出的结果

样例输入

(2+2)^(1+1)

样例输出

16

数据范围与约定

• 表达式总长度<=30

题解：就是一个中缀转后缀的表达式计算，只不过加了一个^符号，优先级高于*/；

//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
using namespace std;
template <class T>
inline bool scan_d(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}

const int maxn=1e6+10;
stack<int> num;
stack<char> ch;
int len;
int getnum(char a) {
	if(a=='+'||a=='-')
		return 0;
	else if(a=='*'||a=='/')
		return 1;
	else if(a=='^')
		return 2;
	return -1;
}
void count() {
	int a=num.top();
	num.pop();
	if(ch.top()=='+')
		a=num.top()+a;
	else if(ch.top()=='-')
		a=num.top()-a;
	else if(ch.top()=='*')
		a=num.top()*a;
	else if(ch.top()=='/')
		a=num.top()/a;
	else if(ch.top()=='^') {
		int temp=1;
		for(int i=0; i<a; i++)
			temp*=num.top();
		a=temp;
	}
	num.pop();
	num.push(a);
	ch.pop();
}
int main() {
	string s;
	cin>>s;
	if(s[0]=='-')s="0"+s;
	for(int i=2; i<s.size(); i++)
		if(s[i]=='-' && s[i-1]=='(') {
			s.insert(i,"0");
			i++;
		}
	len=s.size();
	for(int i=0; i<len; i++) {
		if(s[i]>='0'&&s[i]<='9') {
			int x=0;
			while(s[i]>='0' && s[i]<='9')
				x=x*10+s[i]-'0',i++;
			num.push(x);
			i--;
		} else if(s[i]==')') {
			while(num.size()>1 && ch.top()!='(') {
				count();//符号出栈即计算 
			}
			if(!ch.empty())
				ch.pop();
		} else if(s[i]=='(') {
			ch.push(s[i]);
		} else {

			while(num.size()>1 && getnum(ch.top())>=getnum(s[i])) {
				count();//符号出栈即计算 
			}
			ch.push(s[i]);
		}
	}
	while (!ch.empty() && ch.top()!='(') {
		count();
	}
	printf("%d\n",num.top());
	return 0;
}