使用Stacks从中缀表达式转换为后缀（C ++） [英] Convert from an infix expression to postfix (C++) using Stacks
本文介绍了使用Stacks从中缀表达式转换为后缀（C ++）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我的讲师给了我一个任务，创建一个程序来转换和中缀表达式使用Stacks的后缀。我做了堆栈类和一些函数来读取中缀表达式。
My lecturer gave me an assignment to create a program to convert and infix expression to postfix using Stacks. I've made the stack classes and some functions to read the infix expression.
但这个函数叫做 convertToPostfix（char * const inFix，char * const postFix）将inFix中的inFix表达式转换为使用堆栈的数组postFix中的后置表达式，不是做它想做的事情。你可以帮助我，告诉我我做错了什么吗？
But this one function, called convertToPostfix(char * const inFix, char * const postFix) which is responsible to convert the inFix expression in the array inFix to the post fix expression in the array postFix using stacks, is not doing what it suppose to do. Can you guys help me out and tell me what I'm doing wrong?
下面的代码中，从inFix转换为postFix的函数是 convertToPostfix（char * const inFix，char * const postFix）是我需要帮助修复：
The following is code where the functions to convert from inFix to postFix is and convertToPostfix(char * const inFix, char * const postFix) is what I need help fixing:
void ArithmeticExpression::inputAndConvertToPostfix()
{
char inputChar; //declaring inputChar
int i = 0; //inizalize i to 0
cout << "Enter the Arithmetic Expression(No Spaces): ";
while( ( inputChar = static_cast<char>( cin.get() ) ) != '\n' )
{
if (i >= MAXSIZE) break; //exits program if i is greater than or equal to 100
if(isdigit(inputChar) || isOperator(inputChar))
{
inFix[i] = inputChar; //copies each char to inFix array
cout << inFix[i] << endl;
}
else
cout << "You entered an invalid Arithmetic Expression\n\n" ;
}
// increment i;
i++;
convertToPostfix(inFix, postFix);
}
bool ArithmeticExpression::isOperator(char currentChar)
{
if(currentChar == '+')
return true;
else if(currentChar == '-')
return true;
else if(currentChar == '*')
return true;
else if(currentChar == '/')
return true;
else if(currentChar == '^')
return true;
else if(currentChar == '%')
return true;
else
return false;
}
bool ArithmeticExpression::precedence(char operator1, char operator2)
{
if ( operator1 == '^' )
return true;
else if ( operator2 == '^' )
return false;
else if ( operator1 == '*' || operator1 == '/' )
return true;
else if ( operator1 == '+' || operator1 == '-' )
if ( operator2 == '*' || operator2 == '/' )
return false;
else
return true;
return false;
}
void ArithmeticExpression::convertToPostfix(char * const inFix, char * const postFix)
{
Stack2<char> stack;
const char lp = '(';
stack.push(lp); //Push a left parenthesis ‘(‘ onto the stack.
strcat(inFix,")");//Appends a right parenthesis ‘)’ to the end of infix.
// int i = 0;
int j = 0;
if(!stack.isEmpty())
{
for(int i = 0;i < 100;){
if(isdigit(inFix[i]))
{
postFix[j] = inFix[i];
cout << "This is Post Fix for the first If: " << postFix[j] << endl;
i++;
j++;
}
if(inFix[i] == '(')
{
stack.push(inFix[i]);
cout << "The InFix was a (" << endl;
i++;
//j++;
}
if(isOperator(inFix[i]))
{
char operator1 = inFix[i];
cout << "CUrrent inFix is a operator" << endl;
if(isOperator(stack.getTopPtr()->getData()))
{
cout << "The stack top ptr is a operator1" << endl;
char operator2 = stack.getTopPtr()->getData();
if(precedence(operator1,operator2))
{
//if(isOperator(stack.getTopPtr()->getData())){
cout << "The stack top ptr is a operato2" << endl;
postFix[j] = stack.pop();
cout << "this is post fix " << postFix[j] << endl;
i++;
j++;
// }
}
}
else
stack.push(inFix[i]);
// cout << "Top Ptr is a: "<< stack.getTopPtr()->getData() << endl;
}
for(int r = 0;r != '\0';r++)
cout << postFix[r] << " ";
if(inFix[i] == ')')
{
while(stack.stackTop()!= '(')
{
postFix[j] = stack.pop();
i++;
j++;
}
stack.pop();
}
}
}
}
注意函数convertToPostfix使用此算法进行：
Note the function convertToPostfix was made using this algorithm:
- 将一个左括号''放入堆栈。
-
当堆栈不为空时，从左向右读取中缀并执行以下操作：
- Push a left parenthesis ‘(‘ onto the stack.
- Append a right parenthesis ‘)’ to the end of infix.
While the stack is not empty, read infix from left to right and do the following:
- 如果中缀中的当前字符是数字，请将其复制到后缀的下一个元素。
- 如果当前
-
如果infix中的当前字符是运算符，
- If the current character in infix is a digit, copy it to the next element of postfix.
- If the current character in infix is a left parenthesis, push it onto the stack.
If the current character in infix is an operator,
- 在堆栈顶部的pop操作符（如果有的话），它们具有与当前操作符相同或更高的优先级，并在后缀中插入弹出的操作符。
- 将中缀中的当前字符推入堆栈。
- 从栈顶顶部填充操作符，并将其插入后缀，直到左括号在堆栈顶部。
- 从堆栈中弹出（并丢弃）左括号。
推荐答案
这基本上是对Yuushi答案的评论。
This is basically a comment to the answer from Yuushi.
- 外部while（！stack.empty（））循环是错误的。只是删除它。 （保持c的循环体）。在函数结束时，检查堆栈是否为空，否则表达式有语法错误。
- 由于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 +
- The outer while(!stack.empty()) loop is wrong. just remove it. (keep the loop body ofc). At the end of the function, check that the stack is empty, else the expression had syntax errors.
- As Yuushi already said the precedence function looks bogus. First you should give the parameters better names: one is the operator to the left, and the other to the right. (Right now you call it
precedence(rightOp, leftOp)). Then you should document what the result means - right now you return true ifa 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). - If you find a new operator you need to loop over the old operators on the stack, for example after reading
a - b * cyour output isa b cand the stack is[- *]. now you read a+, and you need to pop both operators, resulting ina b c * -. I.e., the inputa - b * c + dshould result ina 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;
}
这篇关于使用Stacks从中缀表达式转换为后缀（C ++）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
