更新时间:2023-02-18 12:52:08
这基本上是对Yuushi答案的评论。
This is basically a comment to the answer from Yuushi.
优先(rightOp,leftOp)
)。然后你应该记录结果的意思 - 现在你返回true如果一个rOp b lOp c ==(a rOp b)lOp c
(是的,操作顺序doesn'例如,两个订单中的+和 - 不相同)。 a - b * c
后,您的输出为 abc
,堆栈为 [ - *]
。现在你读一个 +
,你需要弹出两个运算符,导致 a b c * -
。即,输入 a - b * c + d
应导致 abc * - d +
precedence(rightOp, leftOp)
). Then you should document what the result means - right now you return true if a rOp b lOp c == (a rOp b) lOp c
(yes, the operator order doesn't match what you call - "+" and "-" are not the same in both orders for example).a - b * c
your output is a b c
and the stack is [- *]
. now you read a +
, and you need to pop both operators, resulting in a b c * -
. I.e., the input a - b * c + d
should result in a b c * - d +
更新:附加完整解决方案(基于Yuushi的回答):
Update: appended complete solution (based on Yuushi's answer):
bool isOperator(char currentChar)
{
switch (currentChar) {
case '+':
case '-':
case '*':
case '/':
case '^':
case '%':
return true;
default:
return false;
}
}
// returns whether a `lOp` b `rOp` c == (a `lOp` b) `rOp` c
bool precedence(char leftOperator, char rightOperator)
{
if ( leftOperator == '^' ) {
return true;
} else if ( rightOperator == '^' ) {
return false;
} else if ( leftOperator == '*' || leftOperator == '/' || leftOperator == '%' ) {
return true;
} else if ( rightOperator == '*' || rightOperator == '/' || rightOperator == '%' ) {
return false;
}
return true;
}
#include <stdexcept>
#include <cctype>
#include <sstream>
#include <stack>
std::string convertToPostfix(const std::string& infix)
{
std::stringstream postfix; // Our return string
std::stack<char> stack;
stack.push('('); // Push a left parenthesis ‘(‘ onto the stack.
for(std::size_t i = 0, l = infix.size(); i < l; ++i) {
const char current = infix[i];
if (isspace(current)) {
// ignore
}
// If it's a digit or '.' or a letter ("variables"), add it to the output
else if(isalnum(current) || '.' == current) {
postfix << current;
}
else if('(' == current) {
stack.push(current);
}
else if(isOperator(current)) {
char rightOperator = current;
while(!stack.empty() && isOperator(stack.top()) && precedence(stack.top(), rightOperator)) {
postfix << ' ' << stack.top();
stack.pop();
}
postfix << ' ';
stack.push(rightOperator);
}
// We've hit a right parens
else if(')' == current) {
// While top of stack is not a left parens
while(!stack.empty() && '(' != stack.top()) {
postfix << ' ' << stack.top();
stack.pop();
}
if (stack.empty()) {
throw std::runtime_error("missing left paren");
}
// Discard the left paren
stack.pop();
postfix << ' ';
} else {
throw std::runtime_error("invalid input character");
}
}
// Started with a left paren, now close it:
// While top of stack is not a left paren
while(!stack.empty() && '(' != stack.top()) {
postfix << ' ' << stack.top();
stack.pop();
}
if (stack.empty()) {
throw std::runtime_error("missing left paren");
}
// Discard the left paren
stack.pop();
// all open parens should be closed now -> empty stack
if (!stack.empty()) {
throw std::runtime_error("missing right paren");
}
return postfix.str();
}
#include <iostream>
#include <string>
int main()
{
for (;;) {
if (!std::cout.good()) break;
std::cout << "Enter the Arithmetic Expression: ";
std::string infix;
std::getline(std::cin, infix);
if (infix.empty()) break;
std::cout << "Postfix: '" << convertToPostfix(infix) << "'\n";
}
return 0;
}