题目
=================================================
问题描述
输入一个只包含加减乖除和括号的合法表达式，求表达式的值。
输入格式
输入一行，包含一个表达式。
输出格式
输出这个表达式的值。
样例输入
31*(5-22)+70*(3-21)/32
样例输出
-55.8438
数据规模和约定
表达式长度不超过100，表达式运算合法。
两个步骤：输入、处理。
需要注意的地方：除法的double和判0。
用栈实现
=================================================
先将中缀转后缀。具体步骤是：
遇数值就计算value,输出并存到ssuffix里。
遇到操作数+-*/就存到栈里。
遇到左括号就递归使用trans。
遇到右括号就pop栈，并把pop的值存到ssuffix里。
后缀计算就比较简单了：
遇数值就存到value栈。
遇操作数就value.pop()两次。再把运算结果存到value栈里。
最后循环最外输出value里仅存的值，就是答案。
这里使用的是标准库stack，代码如下：
#include <bits/stdc++.h>
#include <stack>
using namespace std;//31*(5-22)+70*(3-21)/32
stack<char> s;
int i = 0;
char ssuffix[105];
int slen = 0;
void trans(string str){//中缀转后缀
int value;
int len = str.length();
char temp;
for(; i < len; i++){
value = 0;
if(str[i] == ')' || str[i] == '#'){
while(!s.empty()){
cout << s.top() << " ";
ssuffix[slen++] = s.top();
s.pop();
}
return;
}
while(isdigit(str[i])){
value = 10 * value + str[i] - '0';
temp = str[i+1];
if((!isdigit(temp))||i+1 >= len){
cout << value << " ";
ssuffix[slen++] = value;
break;
}
i++;
}
if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/'){
s.push(str[i]);
}
if(str[i] == '('){
i++;
trans(str);
}
}
while(!s.empty()){
cout << s.top() << " ";
ssuffix[slen++] = s.top();
s.pop();
}
}
void calculate(char s[], int len){//后缀，计算值
stack <double> value;
char c;
double ans;
for(int j = 0; j < slen; j++){
c = ssuffix[j];
if(c == '+' || c== '-'|| c== '*'|| c== '/'){
switch(c){
case '+':
ans = value.top();
value.pop();
ans += value.top();
value.pop();
value.push(ans);
break;
case '-':
ans = value.top();
value.pop();
ans = value.top() - ans;
value.pop();
value.push(ans);
break;
case '*':
ans = value.top();
value.pop();
ans = value.top() * ans;
value.pop();
value.push(ans);
break;
case '/':
ans = value.top();
if(ans - 0 < 1e-6) return;
value.pop();
ans = value.top() / ans;
value.pop();
value.push(ans);
break;
}
}else{
value.push(double(ssuffix[j]));
}
}
cout << value.top() << endl;
}
int main(){
string str;
cin >> str;
cout << "The infix expression is: ";
cout << str << endl;
cout << "The suffix expression is: ";
trans(str);
cout << endl;
cout << "The answer is: ";
calculate(ssuffix, slen);
} 用函数递归实现
=================================================
代码如下：
#include <bits/stdc++.h>
using namespace std;
int expression();
int term();
int factor();
int expression(){
int result = term();
while(1){
char op = cin.peek();
if(op == '+' || op == '-'){
cin.get();
int value = term();
if(op == '+'){
result += value;
}else result -= value;
}else break;
}
return result;
}
int term(){
int result = factor();
while(1){
char op = cin.peek();
if(op == '*' || op == '/'){
cin.get();
int value = factor();
if(op == '*'){
result *= value;
}else result /= value;
}else break;
}
return result;
}
int factor(){
int result = 0;
char c = cin.peek();
if(c == '('){
cin.get();
result = expression();
cin.get();
}else{
while(isdigit(c)){
result = 10 * result + c - '0';
cin.get();
c = cin.peek();
}
}
return result;
}
int main(){
cout << expression() << endl;
system("pause");
}