11033: 【原1033】表达式求值
题目
题目描述
author: zyz 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1033
Description
二哥想自己做一个计算器，但是他需要一个程序来计算输入表达式的结果。你能帮助他吗？
Input Format
输入仅一行，给出一个算数表达式。表达式中包含：小括号，加减乘除，指数运算符，负号，整数，空格。其中负号的优先级最高(-)，其次是指数运算(^)，然后是乘除(*/)，最后是加减(+-)。
这里规定除法为整除运算，如 5 / 2 = 2, 8 / -3 = -2 等等，与C++中的整除一致。另外注意指数运算为右结合，即 2^3^2 = 2^9 = 512 而非 2^3^2 = 8^2 = 64 。
输入的字符串长度不超过100。
Output Format
如果输入的表达式出现括号不匹配或者除零错误，输出一行“Error”（不含引号），否则输出运算结果。输入保证不包含任何其它类型的错误。
输入的数，输出的答案，以及中间结果均保证是不超过 long long 范围的整数。
Sample Input
5 + (1 + 3) * 6 ^ 1
Sample Output
29
Sample Input
(6 + 2)) * 3
Sample Output
Error
说明
30%的测试数据含有负号；
30%的测试数据含有指数运算。
FineArtz's solution
/* 表达式求值 */
#include <iostream>
#include <cmath>
#include <stdexcept>
using namespace std;
enum OptType {ADD, SUB, MUL, DIV, BRACKET, EXP, POS, NEG, NONE};
enum TokenType {DIGIT, OPT, VOID};
class Opt{
public:
Opt() : opt(' '), type(NONE), predency(-2) {}
Opt(char ch) : opt(ch){
switch(ch){
case '+':
type = ADD;
predency = 1;
break;
case '-':
type = SUB;
predency = 1;
break;
case '*':
type = MUL;
predency = 2;
break;
case '/':
type = DIV;
predency = 2;
break;
case '(':
type = BRACKET;
predency = 0;
break;
case '^':
type = EXP;
predency = 3;
break;
case '&':
type = POS;
predency = 4;
break;
case '|':
type = NEG;
predency = 4;
break;
case ')':
type = BRACKET;
predency = 10;
break;
default:
throw runtime_error("fuck it");
break;
}
}
OptType getType() { return type; }
int getPred() { return predency; }
char getOpt() { return opt; }
private:
char opt;
OptType type;
int predency;
};
long long qpow(long long x, long long n){
long long ans = 1, tmp =x;
while (n > 0){
if (n & 1) ans *= tmp;
n >>= 1;
tmp *= tmp;
}
return ans;
}
long long operate(long long x, long long y, Opt opt){
switch(opt.getOpt()){
case '+':
return x + y;
case '-':
return x - y;
case '*':
return x * y;
case '/':
if (y == 0) throw runtime_error("fuck it");
return x / y;
case '^':
return qpow(x, y);
default:
throw runtime_error("fuck it");
}
}
char suf[200];
int sufSize = 0;
void infToSuf(){
char ch;
long long curNum = 0x7fffffff;
TokenType lastTokenType = VOID;
Opt optStack[200];
int optSize = 0;
while (cin >> ch){
if (isdigit(ch)){
if (curNum == 0x7fffffff) curNum = 0;
curNum = curNum * 10 + ch - '0';
lastTokenType = DIGIT;
}
else{
if (lastTokenType == DIGIT && curNum != 0x7fffffff){
if (curNum != 0){
int dec = ceil(log10(curNum));
if (abs(dec - log10(curNum)) < 1e-6) ++dec;
while (dec > 0){
suf[sufSize++] = curNum / qpow(10, dec - 1) + '0';
curNum %= qpow(10, dec - 1);
--dec;
}
}
else{
suf[sufSize++] = '0';
}
curNum = 0x7fffffff;
suf[sufSize++] = '#';
}
Opt curOpt(ch);
switch(curOpt.getOpt()){
case ')':
while (optSize > 0 && optStack[optSize - 1].getOpt() != '('){
suf[sufSize++] = optStack[--optSize].getOpt();
}
if (optSize == 0){
throw runtime_error("fuck it");
}
if (optStack[--optSize].getOpt() != '('){
throw runtime_error("fuck it");
}
lastTokenType = DIGIT;
break;
case '(':
optStack[optSize++] = curOpt;
lastTokenType = OPT;
break;
case '-': case '+':
if (lastTokenType == VOID || lastTokenType == OPT){
lastTokenType = OPT;
if (curOpt.getOpt() == '-'){
Opt tmpOpt('|');
optStack[optSize++] = tmpOpt;
}
else{
Opt tmpOpt('&');
optStack[optSize++] = tmpOpt;
}
break;
}
case '*': case '/':
if (optSize == 0 || curOpt.getPred() > optStack[optSize - 1].getPred()){
optStack[optSize++] = curOpt;
}
else{
while (optSize > 0 && curOpt.getPred() <= optStack[optSize - 1].getPred()){
suf[sufSize++] = optStack[--optSize].getOpt();
}
optStack[optSize++] = curOpt;
}
lastTokenType = OPT;
break;
case '^':
if (optSize == 0 || curOpt.getPred() >= optStack[optSize - 1].getPred()){
optStack[optSize++] = curOpt;
}
else{
while (optSize > 0 && curOpt.getPred() < optStack[optSize - 1].getPred()){
suf[sufSize++] = optStack[--optSize].getOpt();
}
optStack[optSize++] = curOpt;
}
lastTokenType = OPT;
break;
}
}
}
if (lastTokenType == DIGIT && curNum != 0x7fffffff){
if (curNum != 0){
int dec = ceil(log10(curNum));
if (abs(dec - log10(curNum)) < 1e-6) ++dec;
while (dec > 0){
suf[sufSize++] = curNum / qpow(10, dec - 1) + '0';
curNum %= qpow(10, dec - 1);
--dec;
}
}
else{
suf[sufSize++] = '0';
}
curNum = 0x7fffffff;
suf[sufSize++] = '#';
}
while (optSize > 0){
if (optStack[--optSize].getOpt() == '('){
throw runtime_error("fuck it");
}
suf[sufSize++] = optStack[optSize].getOpt();
}
}
long long calcSuf(){
long long numStack[200];
int numSize = 0;
int curPos = 0;
long long curNum = 0x7fffffff;
while (curPos < sufSize){
while (isdigit(suf[curPos])){
if (curNum == 0x7fffffff) curNum = 0;
curNum = curNum * 10 + suf[curPos++] - '0';
}
if (suf[curPos] == '#') ++curPos;
if (curNum != 0x7fffffff){
numStack[numSize++] = curNum;
curNum = 0x7fffffff;
}
if (isdigit(suf[curPos]))
continue;
Opt curOpt(suf[curPos++]);
long long opr1 = 0, opr2 = 0;
switch(curOpt.getOpt()){
case '+': case '-': case '*': case '/': case '^':
if (numSize < 2) throw runtime_error("fuck it");
opr2 = numStack[--numSize];
opr1 = numStack[--numSize];
numStack[numSize++] = operate(opr1, opr2, curOpt);
break;
case '&': case '|':
if (numSize < 1) throw runtime_error("fuck it");
if (curOpt.getOpt() == '|')
numStack[numSize - 1] = -numStack[numSize - 1];
break;
default:
throw runtime_error("fuck it");
break;
}
}
return numStack[0];
}
int main(){
try{
infToSuf();
}
catch(runtime_error){
cout << "Error" << endl;
return 0;
}
try{
cout << calcSuf() << endl;
}
catch(runtime_error){
cout << "Error" << endl;
return 0;
}
return 0;
}
q4x3's solution
/**
* 计算器
* longlong
* 不判-1 1 0会超时
* -1 ^ 2 = 1 (这就尼玛离谱)
* 脑子有病的一个题
**/
#include <iostream>
#include <stdio.h>
using namespace std;
struct stk {
char dat[233];
int top;
};
struct istk {
long long dat[233];
int top;
};
char tot[233], tmp;
char pre, cur;
long long cnt, head, flag = 1;
int main() {
while(1) {
tmp = getchar();
if(tmp == ' ') continue;
if(tmp == '\n') {
tot[cnt ++] = 0;
break;
} else {
tot[cnt ++] = tmp;
}
}
stk tok;
istk num;
tok.top = -1;
num.top = -1;
while(1) {
if(head + 1 == cnt) break;
pre = cur;
cur = tot[head ++];
if(cur > '9' || cur < '0') {
if(cur == '-') {
if(pre == 0 || pre == '(' || pre == '*' || pre == '/' || pre == '^' || pre == '+' || pre == '-') {
tok.dat[++ tok.top] = '|';
} else {
while(tok.top != -1 && tok.dat[tok.top] != '(') {
long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
if(tok.dat[tok.top] == '+') {
num.dat[num.top - 1] = tmp1 + tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '-') {
num.dat[num.top - 1] = tmp1 - tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '*') {
num.dat[num.top - 1] = tmp1 * tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '/') {
if(tmp2 == 0) {
cout << "Error" << endl;
return 0;
} else {
num.dat[num.top - 1] = tmp1 / tmp2;
-- num.top;
-- tok.top;
}
} else
if(tok.dat[tok.top] == '^') {
long long tmp = 1;
for(int i = 0;i < tmp2;++ i) {
if(tmp1 == 0) {
tmp = 0;
break;
} else if(tmp1 == 1) {
tmp = 1;
break;
} else if(tmp1 == -1) {
if(tmp2 % 2 == 0)
tmp = 1;
else tmp = -1;
break;
}
tmp *= tmp1;
}
num.dat[num.top - 1] = tmp;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '|') {
num.dat[num.top] = - num.dat[num.top];
-- tok.top;
}
}
tok.dat[++ tok.top] = '-';
}
} else
if(cur == '(') {
tok.dat[++ tok.top] = '(';
} else
if(cur == ')') {
while(tok.top != -1 && tok.dat[tok.top] != '(') {
long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
if(tok.dat[tok.top] == '+') {
num.dat[num.top - 1] = tmp1 + tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '-') {
num.dat[num.top - 1] = tmp1 - tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '*') {
num.dat[num.top - 1] = tmp1 * tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '/') {
if(tmp2 == 0) {
cout << "Error" << endl;
return 0;
} else {
num.dat[num.top - 1] = tmp1 / tmp2;
-- num.top;
-- tok.top;
}
} else
if(tok.dat[tok.top] == '^') {
long long tmp = 1;
for(int i = 0;i < tmp2;++ i) {
if(tmp1 == 0) {
tmp = 0;
break;
} else if(tmp1 == 1) {
tmp = 1;
break;
} else if(tmp1 == -1) {
if(tmp2 % 2 == 0)
tmp = 1;
else tmp = -1;
break;
}
tmp *= tmp1;
}
num.dat[num.top - 1] = tmp;
-- num.top;
-- tok.top;
}
if(tok.dat[tok.top] == '|') {
num.dat[num.top] = - num.dat[num.top];
-- tok.top;
}
}
if(tok.dat[tok.top] != '(') {
cout << "Error" << endl;
return 0;
} else {
-- tok.top;
}
} else
if(cur == '^') {
while(tok.top != 1 && tok.dat[tok.top] == '|') {
num.dat[num.top] = - num.dat[num.top];
-- tok.top;
}
tok.dat[++ tok.top] = '^';
} else
if(cur == '*') {
while(tok.top != -1 && tok.dat[tok.top] != '(' && tok.dat[tok.top] != '+' && tok.dat[tok.top] != '-') {
long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
if(tok.dat[tok.top] == '*') {
num.dat[num.top - 1] = tmp1 * tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '/') {
if(tmp2 == 0) {
cout << "Error" << endl;
return 0;
} else {
num.dat[num.top - 1] = tmp1 / tmp2;
-- num.top;
-- tok.top;
}
} else
if(tok.dat[tok.top] == '^') {
long long tmp = 1;
for(int i = 0;i < tmp2;++ i) {
if(tmp1 == 0) {
tmp = 0;
break;
} else if(tmp1 == 1) {
tmp = 1;
break;
} else if(tmp1 == -1) {
if(tmp2 % 2 == 0)
tmp = 1;
else tmp = -1;
break;
}
tmp *= tmp1;
}
num.dat[num.top - 1] = tmp;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '|') {
num.dat[num.top] = - num.dat[num.top];
-- tok.top;
}
}
tok.dat[++ tok.top] = '*';
} else
if(cur == '/') {
while(tok.top != -1 && tok.dat[tok.top] != '(' && tok.dat[tok.top] != '+' && tok.dat[tok.top] != '-') {
long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
if(tok.dat[tok.top] == '*') {
num.dat[num.top - 1] = tmp1 * tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '/') {
if(tmp2 == 0) {
cout << "Error" << endl;
return 0;
} else {
num.dat[num.top - 1] = tmp1 / tmp2;
-- num.top;
-- tok.top;
}
} else
if(tok.dat[tok.top] == '^') {
long long tmp = 1;
for(int i = 0;i < tmp2;++ i) {
if(tmp1 == 0) {
tmp = 0;
break;
} else if(tmp1 == 1) {
tmp = 1;
break;
} else if(tmp1 == -1) {
if(tmp2 % 2 == 0)
tmp = 1;
else tmp = -1;
break;
}
tmp *= tmp1;
}
num.dat[num.top - 1] = tmp;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '|') {
num.dat[num.top] = - num.dat[num.top];
-- tok.top;
}
}
tok.dat[++ tok.top] = '/';
} else
if(cur == '+') {
while(tok.top != -1 && tok.dat[tok.top] != '(') {
long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
if(tok.dat[tok.top] == '+') {
num.dat[num.top - 1] = tmp1 + tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '-') {
num.dat[num.top - 1] = tmp1 - tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '*') {
num.dat[num.top - 1] = tmp1 * tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '/') {
if(tmp2 == 0) {
cout << "Error" << endl;
return 0;
} else {
num.dat[num.top - 1] = tmp1 / tmp2;
-- num.top;
-- tok.top;
}
} else
if(tok.dat[tok.top] == '^') {
long long tmp = 1;
for(int i = 0;i < tmp2;++ i) {
if(tmp1 == 0) {
tmp = 0;
break;
} else if(tmp1 == 1) {
tmp = 1;
break;
} else if(tmp1 == -1) {
if(tmp2 % 2 == 0)
tmp = 1;
else tmp = -1;
break;
}
tmp *= tmp1;
}
num.dat[num.top - 1] = tmp;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '|') {
num.dat[num.top] = - num.dat[num.top];
-- tok.top;
}
}
tok.dat[++ tok.top] = '+';
}
} else {
if(pre > '9' || pre < '0')
num.dat[++ num.top] = cur - '0';
else {
long long tmpi = num.dat[num.top];
tmpi = tmpi * 10 + cur - '0';
num.dat[num.top] = tmpi;
}
}
}
while(tok.top != -1) {
if(tok.dat[tok.top] == '(') {
cout << "Error" << endl;
return 0;
}
long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
if(tok.dat[tok.top] == '+') {
num.dat[num.top - 1] = tmp1 + tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '-') {
num.dat[num.top - 1] = tmp1 - tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '*') {
num.dat[num.top - 1] = tmp1 * tmp2;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '/') {
if(tmp2 == 0) {
cout << "Error" << endl;
return 0;
} else {
num.dat[num.top - 1] = tmp1 / tmp2;
-- num.top;
-- tok.top;
}
} else
if(tok.dat[tok.top] == '^') {
long long tmp = 1;
for(int i = 0;i < tmp2;++ i) {
if(tmp1 == 0) {
tmp = 0;
break;
} else if(tmp1 == 1) {
tmp = 1;
break;
} else if(tmp1 == -1) {
if(tmp2 % 2 == 0)
tmp = 1;
else tmp = -1;
break;
}
tmp *= tmp1;
}
num.dat[num.top - 1] = tmp;
-- num.top;
-- tok.top;
} else
if(tok.dat[tok.top] == '|') {
num.dat[num.top] = - num.dat[num.top];
-- tok.top;
}
}
cout << num.dat[num.top] << endl;
//cout << "Error" << endl;
return 0;
}
victrid's solution
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
//EXCEPTIONS
struct ENOB {};
struct EDIV {};
struct atoma {
//value:
// 1 2 3 4 5 6
// + - * / ^ (-)
//priority level:
// 00111000
// |----------- + - = 1, * / = 2 ^ = 3 - = 4
// |-------- number of digit. (^ in 999-ans)
// |-------------- bracketcount
bool isoperator;
long long value;
int priority;
};
atoma ps[100];
atoma zero{0, 0, 0};
struct tree {
atoma& at;
tree* left;
tree* right;
tree(atoma& a, tree* l, tree* r) : at(a), left(l), right(r){};
~tree() {
if (left != nullptr)
delete left;
if (right != nullptr)
delete right;
}
};
int read() {
char ch = 0;
int
chcount = 0,
bracket = 0,
atomaplace = 0,
digit = 0;
long long totalis = 0;
while (true) {
if (ch < '0' || ch > '9') {
if (digit) {
ps[atomaplace++] = atoma{false, totalis, 0};
}
digit = 0;
totalis = 0;
switch (ch) {
case '+':
ps[atomaplace++] = atoma{true, 1, bracket * 100000 + 10000 + 1000 - chcount};
break;
case '-':
if (atomaplace == 0 || ps[atomaplace - 1].isoperator) {
ps[atomaplace++] = atoma{true, 6, bracket * 100000 + 40000 + 1000 - chcount};
} else
ps[atomaplace++] = atoma{true, 2, bracket * 100000 + 10000 + 1000 - chcount};
break;
case '*':
ps[atomaplace++] = atoma{true, 3, bracket * 100000 + 20000 + 1000 - chcount};
break;
case '/':
ps[atomaplace++] = atoma{true, 4, bracket * 100000 + 20000 + 1000 - chcount};
break;
case '^':
ps[atomaplace++] = atoma{true, 5, bracket * 100000 + 30000 + chcount};
break;
case '(':
bracket++;
break;
case ')':
if (bracket == 0)
throw(ENOB());
bracket--;
break;
case '\n':
//!!!!!!I'm too foolish!
if (bracket != 0)
throw(ENOB());
return atomaplace;
default:
break;
}
ch = getchar();
chcount++;
} else {
digit++;
totalis = totalis * 10 + (ch - '0');
ch = getchar();
chcount++;
}
}
}
tree* search(int left, int right) {
if (left > right)
return new tree(zero, nullptr, nullptr);
if (left == right)
return new tree(ps[left], nullptr, nullptr);
int min = 1e9;
int loc = -1;
for (int i = left; i <= right; i++) {
if (ps[i].priority != 0 && ps[i].priority < min) {
loc = i;
min = ps[i].priority;
}
}
tree* lf = search(left, loc - 1);
tree* rt = search(loc + 1, right);
return new tree(ps[loc], lf, rt);
}
long long integerpow(long long base, long long power) {
long long ans = 1, tmp = base;
while (power > 0) {
if (power & 1)
ans *= tmp;
power >>= 1;
tmp *= tmp;
}
return ans;
}
tree* shorten(tree* root) {
if (!root->at.isoperator) {
return root;
}
shorten(root->left);
shorten(root->right);
switch (root->at.value) {
case 1:
root->at.value = root->left->at.value + root->right->at.value;
break;
case 2:
root->at.value = root->left->at.value - root->right->at.value;
break;
case 3:
root->at.value = root->left->at.value * root->right->at.value;
break;
case 4:
if (root->right->at.value == 0)
throw(EDIV());
root->at.value = root->left->at.value / root->right->at.value;
break;
case 6:
root->at.value = root->left->at.value - root->right->at.value;
break;
case 5:
if (root->right->at.value == 0)
throw(EDIV());
root->at.value = integerpow(root->left->at.value, root->right->at.value);
break;
}
root->at.isoperator = false;
root->at.priority = 0;
delete root->left;
delete root->right;
root->left = nullptr;
root->right = nullptr;
return root;
}
int main() {
int atomacount;
try {
atomacount = read();
} catch (ENOB) {
cout << "Error" << endl;
return 0;
}
tree* lg = search(0, atomacount - 1);
try {
cout << shorten(lg)->at.value << endl;
} catch (EDIV) {
cout << "Error" << endl;
return 0;
}
return 0;
}