作为大学项目的一部分,我写了一个关于 Dijkstra 的 Shutting Yard Algorithm 的尝试。一切都按预期工作,但我还需要展示操作员在处理后是如何排序的,我不知道该怎么做,我相信最好的方法是队列?有谁知道如何做到这一点?我的代码:
// Finding operators
int operators(char op){
if(op == '+'||op == '-')
return 1;
if(op == '*'||op == '/')
return 2;
return 0;
}
// The maths
int maths(int a, int b, char op){
switch(op){
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
return 0;
}
// Returning value of expression
int evaluate(string tokens){
int i;
// stack to store integers and operators.
stack <int> numbers;
stack <char> ops;
for(i = 0; i < tokens.length(); i++){
// if token blank, skip
if(tokens[i] == ' ')
continue;
// if token '(' add to stack
else if(tokens[i] == '('){
ops.push(tokens[i]);
}
// if token is a number, add to stack
else if(isdigit(tokens[i])){
int val = 0;
// single or double digit number.
while(i < tokens.length() &&
isdigit(tokens[i]))
{
val = (val*10) + (tokens[i]-'0');
i++;
}
numbers.push(val);
}
// if token ')', solve entire brace.
else if(tokens[i] == ')')
{
while(!ops.empty() && ops.top() != '(')
{
int val2 = numbers.top();
numbers.pop();
int val1 = numbers.top();
numbers.pop();
char op = ops.top();
ops.pop();
numbers.push(maths(val1, val2, op));
}
// pop opening brace.
ops.pop();
}
// Current token is an operator.
else
{
while(!ops.empty() && operators(ops.top())
>= operators(tokens[i])){
int val2 = numbers.top();
numbers.pop();
int val1 = numbers.top();
numbers.pop();
char op = ops.top();
ops.pop();
numbers.push(maths(val1, val2, op));
}
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
//Do remaining operations
while(!ops.empty()){
int val2 = numbers.top();
numbers.pop();
int val1 = numbers.top();
numbers.pop();
char op = ops.top();
ops.pop();
numbers.push(maths(val1, val2, op));
}
// Top of 'numbers' contains result, return
return numbers.top();
}
int main() {
cout << evaluate("10 + 10 * 10") << "\n";
cout << evaluate("3 + 4 * 2 + ( 23 - 5 )") << "\n";
cout << evaluate("100 * ( 2 + 12 )") << "\n";
cout << evaluate("100 * ( 5 + 8 ) / 7") << "\n";
return 0;
}