逆波兰法-算术表达式语法分析C++
· 阅读需 3 分钟
逆波兰表达式的C++实现。算术表达式求值，支持加减乘除和幂运算，支持圆括号改变优先级。
//后缀表达式练习
//2018-09-20
#include <stack>
#include <iostream>
#include <cstdlib>
#include <string>
#include <math.h>
using namespace std;
//定义优先级
enum Priority {
PRI_IGNORE,//无效字符，忽略
PRI_NUMBER,//操作数
PRI_PLUS,//加减
PRI_DIVIDE,//乘除
PRI_POWER,//幂
PRI_LEFT_PAR,//左圆括号
PRI_RIGTHT_PAR,//右圆括号
};
//取操作符优先级
Priority getPriority(char symbol) {
if ((symbol >= '0' && symbol <= '9') || symbol == '.')
return PRI_NUMBER;
else if (symbol == '+' || symbol == '-')
return PRI_PLUS;
else if (symbol == '*' || symbol == '/')
return PRI_DIVIDE;
else if (symbol == '^')
return PRI_POWER;
else if (symbol == '(')
return PRI_LEFT_PAR;
else if (symbol == ')')
return PRI_RIGTHT_PAR;
else
return PRI_IGNORE;
}
//中缀表达式转后缀表达式
string toSufixExpression(string express) {
stack<char> operendStack;//操作符暂存栈
string output;//输出后缀表达式
//上一操作符的优先级，如果当前处理的操作符优先级低于它则前操作符出栈
Priority lastPriority = PRI_NUMBER;
string::iterator iter = express.begin();
for (; iter != express.end(); ++iter) {
Priority priority = getPriority(*iter);
switch (priority) {
case PRI_IGNORE:
default:
continue;
case PRI_NUMBER:
output.push_back(*iter);
break;
case PRI_PLUS:
case PRI_DIVIDE:
case PRI_POWER:
case PRI_LEFT_PAR:
//遇到符号向前追加间隔符
output.push_back(' ');
while (operendStack.size()) {
if (getPriority(operendStack.top()) < priority || operendStack.top() == '(')
break;
output.push_back(operendStack.top());
operendStack.pop();
}
lastPriority = priority;
operendStack.push(*iter);
break;
case PRI_RIGTHT_PAR:
while (operendStack.size()) {
if (operendStack.top() != '(') {
output.push_back(operendStack.top());
operendStack.pop();
}
else {
operendStack.pop();
break;
}
}
break;
}
}
//处理完毕，剩余操作符出栈
while (operendStack.size()) {
output.push_back(operendStack.top());
operendStack.pop();
}
return output;
}
//计算后缀表达式
double caculate(string express) {
stack<double> calcStack;//计算存储栈
string::iterator iter = express.begin();
while (iter != express.end()) {
//字符串转整形，并压入栈
if (*iter >= '0' && *iter <= '9') {
string number;
do {
number.push_back(*iter);
++iter;
} while ((*iter >= '0' && *iter <= '9') || *iter == '.');
calcStack.push(atoi(number.c_str()));
continue;
}
//间隔符
if (*iter == ' ') {
++iter;
continue;
}
//操作符，执行运算
if (calcStack.size() < 2)
return 0;
double operandOne = calcStack.top();
calcStack.pop();
double operandTwo = calcStack.top();
calcStack.pop();
switch (*iter++) {
case '+':
calcStack.push(operandTwo + operandOne);
break;
case '-':
calcStack.push(operandTwo - operandOne);
break;
case '*':
calcStack.push(operandTwo * operandOne);
break;
case '/':
calcStack.push(operandTwo / operandOne);
break;
case '^':
calcStack.push(pow(operandTwo, operandOne));
break;
default:
calcStack.push(operandTwo);
calcStack.push(operandOne);
break;
}
}
if (calcStack.size() == 1)
return calcStack.top();
return 0;
}
int main() {
cout << "Please enter an expression:" << endl;
string express;//表达式
getline(cin, express);
if (express.empty()) {
cout << "empty express.\n";
return 0;
}
string output = toSufixExpression(express);
cout << caculate(output) << endl;
system("pause");
return 0;
}