©2020-2024 ioDraw All rights reserved
#include<bits/stdc++.h> #define MAX 1010 using namespace std; /*
表达式求值有两步，一步是中缀表达式转后缀表达式，一步是后缀表达式求值。 中缀转后缀： 从左到右遍历中缀表达式的每个数字和符号，
1)若是数字就输出，即成为后缀表达式的一部分。 2)待入栈元素为')'时，弹栈至遇到'('
3)当栈空或当栈顶元素为'('或待入栈的元素为'('时压栈，直接入栈
4)遇到四则运算符号时把若待入栈符号优先级高于栈顶元素，直接入栈；否则，弹栈至待入栈符号优先级高于栈顶元素 后缀求值：
把后缀序列依次入栈，遇到四则运算符号时，出栈最后压进去的两位数字，用后出栈的数字 运算 先出栈的数字， 然后把运算之后的数字压入栈中。直至后缀序列为空。 */
template <class T> class Stack {private: T *data; //数据 long maxSize; //栈的最大存储限度
long top; //栈顶位置 public: Stack(long max = 0) { maxSize = max; data = new
T[maxSize]; top = -1; } bool isFull() { if (top == maxSize - 1) return true;
return false; } bool isEmpty() { if (top == -1) return true; return false; }
bool push(T item) { if (!isFull()) { data[++top] = item; return true; } else
return false; } T pop() //弹栈 { if (!isEmpty()) return data[top--]; return 0; }
T popWithoutDelete()//查看栈顶元素 { if (!isEmpty()) return data[top]; return 0; }
~Stack() {if (data != NULL) delete[]data; } }; char *infixToSuffix(char *strIn)
{ Stack <char>sta(20); char *strOut = new char[MAX];
//输入到strIn[]中，转换后的保存在strOut[]中 int lengthIn = strlen(strIn); int j = -1;
//strOut[]的下标 for (int i = 0; i < lengthIn; i++) { if (strIn[i] < '10' &&
strIn[i] >='0') //当输入的为数字时，保存 { //当数字位数不是一位时，输出的各位数字之间不含空格 while ((strIn[i] <=
'9' && strIn[i] >= '0') || strIn[i] == '.') strOut[++j] = strIn[i++]; i--;
strOut[++j] ='('; //使用'('分隔数字 continue; } //正号、负号的前一个元素必定是'('或无前一元素，如(+15)、(-16)
if ((strIn[i] == '-' || strIn[i] == '+') && (i == 0 || strIn[i - 1] == '(')) {
if(strIn[i] == '-') //+15的情况舍去正号就行 strOut[++j] = strIn[i]; continue; } if
(strIn[i] ==')') //待入栈元素为')'时，弹栈至遇到'(' { while (sta.popWithoutDelete() != '(')
{ strOut[++j] = sta.pop(); strOut[++j] ='('; } sta.pop(); continue; }
//当栈空或当栈顶元素为'('或待入栈的元素为'('时压栈 if (sta.isEmpty() || sta.popWithoutDelete() == '('
|| strIn[i] =='(') { sta.push(strIn[i]); continue; } if (strIn[i] == '-' ||
strIn[i] =='+') //当遇到减法：'-' 、加法：'+'时 { //当遇不到'('或栈不空时，弹栈至遇到'('或栈为空 while
(sta.popWithoutDelete() !='(' && !sta.isEmpty()) { strOut[++j] = sta.pop();
strOut[++j] ='('; } sta.push(strIn[i]); continue; } if (strIn[i] == '*' ||
strIn[i] =='/') //当遇到'*' 、'/'时 { //栈顶元素不是'*'、'/'时即可压栈 while
(sta.popWithoutDelete() =='*' || sta.popWithoutDelete() == '/') { strOut[++j] =
sta.pop(); strOut[++j] ='('; } sta.push(strIn[i]); continue; } } while
(!sta.isEmpty()) { strOut[++j] = sta.pop(); strOut[++j] ='('; } strOut[++j] =
'\0'; return strOut; } int suffixEvaluation(char *out) { Stack <char>s(MAX); int
len = strlen(out); int temp = 0, result = 0; for(int i = 0; i < len; i++) {
//四则运算符号的下一个数据一定是 ( if((out[i] == '+' || out[i] == '-' || out[i] == '*' || out
[i] =='/') && out[i + 1] == '(') { int a = 0, b = 0, e = 0, cnt = 0, flag; char
operation =out[i], arr[MAX]; s.pop(); while(!s.isEmpty() &&
s.popWithoutDelete() !='(') { if(s.popWithoutDelete() == '-') { a = a * (-1);
s.pop(); }else if(s.popWithoutDelete() >= '0' && s.popWithoutDelete() <= '9') a
+=int(s.pop() - 48) * pow(10, e++); } s.pop(); e = 0; while(!s.isEmpty() &&
s.popWithoutDelete() !='(') { if(s.popWithoutDelete() == '-') { b = b * (-1);
s.pop(); }else if(s.popWithoutDelete() >= '0' && s.popWithoutDelete() <= '9') b
+=int(s.pop() - 48) * pow(10, e++); } switch(operation) { case '+': temp = b +
a;break; case '-': temp = b - a; break; case '*': temp = b * a; break; case '/'
: temp = b / a;break; } result = temp; if(temp < 0) { temp = (-1) * temp;
s.push('-'); } while(temp) { arr[cnt++] = char(temp % 10 + 48); temp /= 10; }
for(int k = cnt - 1; k >= 0; k--) s.push(arr[k]); }else s.push(out[i]); } return
result; }int main() { char charIn[MAX]; cin >> charIn; char *out =
infixToSuffix(charIn); cout <<out << endl; int result = suffixEvaluation(out);
cout << result << endl;return 0; } /* input: -2+(-3)*(7-4)+(-84)/4 后缀：
2(3(7(4(-(*(+(84(4(/(+( result: -32 */