Arithmetic expressions come in the form of prefix notation, infix notation, and postfix notation. Prefix expression means that the binary operator is placed before the two operands. For example, the prefix expression of
2 + 3*(7-4) + 8/4is:+ + 2 * 3 - 7 4 / 8 4. Please design a program to calculate the result value of the prefix expression.
Input format:
Enter a prefix expression giving no more than 30 characters in one line, including only
+,-,*,/and operands, different objects (operands, operation symbols) are separated by spaces.
Output format:
Output the operation result of the prefix expression, retaining 1 digit after the decimal point, or the error message
ERROR.
Input sample:
+ + 2 * 3 - 7 4 / 8 4
Output sample:
13.0
Core idea:
After learning the knowledge of the stack, you must be able to apply it. For this question, first input a string of characters in the form of a string, then use the string strlen function to find the length of the string, and traverse the string from right to left. If the input is a string , you need to convert its type to double type. After getting the double type data, remember to push it onto the stack. When string traversal encounters an operator, there must be at least two data in the stack at this time. Perform the operation, and the operation result is pushed onto the stack again. Repeat this until finally, there is only the last number left on the stack, which is the final result.
Note: When compiled with VS, the gets function should be the same as the scanf function, with the suffix _s, gets_s added.
Here are a few more examples. Students who want to learn more can try:
2.1 / 9 - - 8 4 4
- + 2.8 -1.2 * 6.32 100
The results are, ERROR (the divisor is 0), -630.4
Reference Code:
Method 1: (Loop)
(Relatively easy to understand) (I gave a detailed explanation, I hope novices can understand it, because I am also a novice. In the loop statement, I assume that the input string data has two types: 129 & 3.141, With two cycles and two comparisons, readers can understand the purpose of each cycle step more intuitively)
// Find the value of the prefix expression (enter a prefix expression and calculate its value)
// @ Method 1: Relatively easy to understand
#include <stdio.h>
#include <string.h>
#include <stdlib.h> // @ strlen, gets, puts functions
#define maxsize 35
typedef struct SNode* stack; // @ stack pointer
struct SNode // @ stack node
{
double data[maxsize]; // @ Create a stack to store double type data in the input string
int top; // @ The top of the stack is of int type, not a pointer type
};
stackcreat()
{
stack s = (stack)malloc(sizeof(struct SNode));
s->top = -1;
return s;
}
void push(stack s, double x) // @ Push to the stack
{
s->data[ + + s->top] = x;
}
double pop(stack s) // @ pop out of the stack
{
return s->data[s->top--];
}
void calculate(stack s, double op1, double op2, char str)
{
switch (str) {
case ' + ':
push(s, op1 + op2); // @ function does not contain a return value and has a push operation on the stack itself
break;
case '-':
push(s, op1 - op2);
break;
case '*':
push(s, op1 * op2);
break;
case '/':
push(s, op1 / op2);
break;
default:
break;
}
}
char a[maxsize];
int main()
{
gets(a); // @ input
int l = strlen(a); // @ character length
stack s = creat();
int i = l - 1;
for (int i = l - 1; i >= 0; i--) // @ push onto the stack from right to left
{
if (a[i] >= '0' & amp; & amp; a[i] <= '9') // @ If it is a number, such as 129 & amp; 3.141
{
double x = a[i] - '0';//char->double @ type conversion x at this time: 9 & amp; 1
double m = 10; // Preparing decimals
i = i - 1; // @ because we need to get the characters before a[i] below
for (; i >= 0; i--) // @ i--, so the following a[i] is the character before the number
{
if (a[i] >= '0' & amp; & amp; a[i] <= '9') // @ is preceded by a number, either a decimal or greater than 9
{
x + = m * (a[i] - '0'); // @ For this operation, x = a two-digit number x at this time: 29 & amp; 41
m *= 10; // @ If we loop again, x will be * 100, so m*=10 loops again, x at this time: 129 & amp; 141
}
else if (a[i] == '.') //The decimal point indicates that this number is a decimal
{
x /= m; // @ x does not loop to this point & 0.141 (double type)
m = 1; // @rename m = 1
}
else if (a[i] == '-') //Negative number symbol indicates that this number is negative
{
x = -x;
}
else break; // @ Four situations
}
push(s, x); // @ The loop ends, don’t forget to push it onto the stack. x at this time: 129 & 3.141 pushed onto the stack!
}
else if (a[i] == ' + ' || a[i] == '-' || a[i] == '*' || a[i] == ' /')
{ // @ is not a number, but an operator
double op1 = pop(s);
double op2 = pop(s);
if (a[i] == '/' & amp; & amp; op2 == 0) // @ Don’t forget, if you encounter 0 as the dividend, it is worth 7 points
{
printf("ERROR");
return 0; // @ accounts for two points alone, "abnormal exit", you must return 0 in advance; exit, otherwise the following loop will collapse
}
calculate(s, op1, op2, a[i]);
} // @recycle
}
if (s->top == 0) // @ Ensure: the stack has only the last element, which is the final answer
printf("%.1f\\
", pop(s));
else
printf("ERROR");
return 0;
}
Method 2: (recursive)
(The code is concise and difficult to understand)
(I don’t understand recursion either. I’m satisfied knowing the first method)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
double exp();
int main()
{
printf("%.1f", exp());
return 0;
}
doubleexp()
{
char a[10];
scanf("%s", a, 10);
if (!a[1]) // @ a[1] == 0
{
switch (a[0])
{
case ' + ':
return exp() + exp();
case '-':
return exp() - exp();
case '*':
return exp() * exp();
case '/':
{
double fenzi = exp(); // @numerator
double fenmu = exp(); // @ denominator
if (fenmu != 0) return fenzi / fenmu;
else
{
printf("ERROR");
exit(0);
}
}
default:
return atof(a);
}
}
else
{
if (a[0] == '-' || a[0] == ' + ')
{
char flag = a[0];
int i = 0;
while (a[i])
{
a[i] = a[i + 1];
i + + ;
}
if (flag == '-')
return 0 - atof(a);
else return atof(a);
}
else return atof(a);
}
}
Review the past and learn the new
11.1 Review
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxsize 30
typedef struct
{
double arr[Maxsize];
int top;
}SNode;
typedef SNode* Stack;
StackStackCreat()
{
Stack s = (Stack)malloc(sizeof(SNode));
s->top = -1;
return s;
}
void push(Stack s, double x)
{
s->arr[ + + s->top] = x;
}
double pop(Stack s)
{
return s->arr[s->top--];
}
int main()
{
Stack s = StackCreat();
char str[Maxsize];
gets(str);
int l = strlen(str); // @ is not written out
int i = l--;
for (; i >= 0; i--)
{
if (str[i] >= '0' & amp; & amp; str[i] <= '9')
{
double x = str[i] - '0'; // @ should be outside the loop!
double m = 10;
for (i--; i >= 0; i--)
{
if (str[i] <= '9' & amp; & amp; str[i] >= '0')
{
x = x + (str[i] - '0') * m;
m = m * 10;
}
else if (str[i] == '.')
{
x = x / m;
m = 1;
}
else if (str[i] == '-')
x = -x;
else
break;
}
push(s, x);
}
else if (str[i] == ' + ')
push(s, pop(s) + pop(s));
else if (str[i] == '-')
push(s, pop(s) - pop(s));
else if (str[i] == '*')
push(s, pop(s) * pop(s));
else if (str[i] == '/')
{
double num1 = pop(s), num2 = pop(s);
if (num2 == 0)
{
printf("ERROR"); // @ must be written
return 0; // @ alone accounts for two points, "abnormal exit",
//Return 0 in advance; exit, otherwise the following loop will collapse
}
else
push(s, num1 / num2);
}
}
if (s->top == 0)
printf("%.1f", pop(s));
else
printf("ERROR");
}
It’s not easy to make, can you give me a like and support? Your encouragement is my biggest motivation to move forward!